5.E: Graph Theory (Exercises)
- Page ID
- 15344
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
\( \def\d{\displaystyle}\)
\( \newcommand{\f}[1]{\mathfrak #1}\)
\( \newcommand{\s}[1]{\mathscr #1}\)
\( \def\N{\mathbb N}\)
\( \def\B{\mathbf{B}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\Z{\mathbb Z}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\Q{\mathbb Q}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\R{\mathbb R}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\C{\mathbb C}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\F{\mathbb F}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\A{\mathbb A}\)
\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)
\( \def\X{\mathbb X}\)
\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)
\( \def\E{\mathbb E}\)
\( \def\O{\mathbb O}\)
\( \def\U{\mathcal U}\)
\( \def\pow{\mathcal P}\)
\( \def\inv{^{-1}}\)
\( \def\nrml{\triangleleft}\)
\( \def\st{:}\)
\( \def\~{\widetilde}\)
\( \def\rem{\mathcal R}\)
\( \def\sigalg{$\sigma$-algebra }\)
\( \def\Gal{\mbox{Gal}}\)
\( \def\iff{\leftrightarrow}\)
\( \def\Iff{\Leftrightarrow}\)
\( \def\land{\wedge}\)
\( \def\And{\bigwedge}\)
\( \def\entry{\entry}\)
\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)
\( \def\Vee{\bigvee}\)
\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)
\( \def\imp{\rightarrow}\)
\( \def\Imp{\Rightarrow}\)
\( \def\Fi{\Leftarrow}\)
\( \def\var{\mbox{var}}\)
\( \def\Th{\mbox{Th}}\)
\( \def\entry{\entry}\)
\( \def\sat{\mbox{Sat}}\)
\( \def\con{\mbox{Con}}\)
\( \def\iffmodels{\bmodels\models}\)
\( \def\dbland{\bigwedge \!\!\bigwedge}\)
\( \def\dom{\mbox{dom}}\)
\( \def\rng{\mbox{range}}\)
\( \def\isom{\cong}\)
\(\DeclareMathOperator{\wgt}{wgt}\)
\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)
\( \newcommand{\va}[1]{\vtx{above}{#1}}\)
\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)
\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)
\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)
\( \renewcommand{\v}{\vtx{above}{}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)
\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)
\( \def\ansfilename{practice-answers}\)
\( \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\)
\( \renewcommand{\bar}{\overline}\)
\( \newcommand{\card}[1]{\left| #1 \right|}\)
\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\( \newcommand{\lt}{<}\)
\( \newcommand{\gt}{>}\)
\( \newcommand{\amp}{&}\)
\( \newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\)
\(\renewcommand{\bar}{\overline}\)
\(\newcommand{\card}[1]{\left| #1 \right|}\)
\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\(\newcommand{\lt}{<}\)
\(\newcommand{\gt}{>}\)
\(\newcommand{\amp}{&}\)
5.2: Definitions
1
If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theory?
- Answer
-
This is asking for the number of edges in \(K_{10}\text{.}\) Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is \(90\text{.}\) However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.
2
Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group?
- Answer
-
It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph \(C_5\)). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.
3
Is it possible for two different (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for example)? Draw two such graphs or explain why not.
- Answer
-
Yes. For example, both graphs below contain 6 vertices, 7 edges, and have degrees (2,2,2,2,3,3).
4
Are the two graphs below equal? Are they isomorphic? If they are isomorphic, give the isomorphism. If not, explain.
- Graph 1: \(V = \{a,b,c,d,e\}\text{,}\) \(E = \{\{a,b\}, \{a,c\}, \{a,e\}, \{b,d\}, \{b,e\}, \{c,d\}\}\text{.}\)
- Graph 2:
- Answer
-
The graphs are not equal. For example, graph 1 has an edge \(\{a,b\}\) but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is \(f:G_1 \to G_2\) defined by \(f(a) = d\text{,}\) \(f(b) = c\text{,}\) \(f(c) = e\text{,}\) \(f(d) = b\text{,}\) \(f(e) = a\text{.}\)
5
Consider the following two graphs:
\(G_1\)
- \(V_1=\{a,b,c,d,e,f,g\}\)
- \(E_1=\{\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},\{b,f\},\{c,g\},\{d,e\},\)
- \(\{e,f\},\{f,g\}\}\text{.}\)
\(G_2\)
- \(V_2=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\text{,}\)
- \(E_2=\{\{v_1,v_4\},\{v_1,v_5\},\{v_1,v_7\},\{v_2,v_3\},\{v_2,v_6\},\)
- \(\{v_3,v_5\},\{v_3,v_7\},\{v_4,v_5\},\{v_5,v_6\},\{v_5,v_7\}\}\)
-
Let \(f:G_1 \rightarrow G_2\) be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:
\(x\) \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\) \(f(x)\) \(v_4\) \(v_5\) \(v_1\) \(v_6\) \(v_2\) \(v_3\) \(v_7\) Does \(f\) define an isomorphism between Graph 1 and Graph 2? Explain.
-
Define a new function \(g\) (with \(g\not=f\)) that defines an isomorphism between Graph 1 and Graph 2.
-
Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.
6
Which of the graphs below are bipartite? Justify your answers.
- Answer
-
Three of the graphs are bipartite. The one which is not is \(C_7\) (second from the right). To see that the three graphs are bipartite, we can just give the bipartition into two sets \(A\) and \(B\text{,}\) as labeled below:
The graph \(C_7\) is not bipartite because it is an odd cycle. You would want to put every other vertex into the set \(A\text{,}\) but if you travel clockwise in this fashion, the last vertex will also be put into the set \(A\text{,}\) leaving two \(A\) vertices adjacent (which makes it not a bipartition).
7
For which \(n \ge 3\) is the graph \(C_n\) bipartite?
8
For each of the following, try to give two different unlabeled graphs with the given properties, or explain why doing so is impossible.
- Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles.
- Two different graphs with 8 vertices all of degree 2.
- Two different graphs with 5 vertices all of degree 4.
- Two different graphs with 5 vertices all of degree 3.
- Answer
-
- For example:
- This is not possible if we require the graphs to be connected. If not, we could take \(C_8\) as one graph and two copies of \(C_4\) as the other.
- Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph \(K_5\text{.}\)
- This is not possible. In fact, there is not even one graph with this property (such a graph would have \(5\cdot 3/2 = 7.5\) edges).
5.3: Planar Graphs
1
Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces? Explain.
2
The graph \(G\) has 6 vertices with degrees \(2, 2, 3, 4, 4, 5\text{.}\) How many edges does \(G\) have? Could \(G\) be planar? If so, how many faces would it have. If not, explain.
3
I'm thinking of a polyhedron containing 12 faces. Seven are triangles and four are quadralaterals. The polyhedron has 11 vertices including those around the mystery face. How many sides does the last face have?
- Answer
-
Say the last polyhedron has \(n\) edges, and also \(n\) vertices. The total number of edges the polyhedron has then is \((7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}\) In particular, we know the last face must have an odd number of edges. We also have that \(v = 11 \text{.}\) By Euler's formula, we have \(11 - (37+n)/2 + 12 = 2\text{,}\) and solving for \(n\) we get \(n = 5\text{,}\) so the last face is a pentagon.
4
Consider some classic polyhedrons.
- An octahedron is a regular polyhedron made up of 8 equilateral triangles (it sort of looks like two pyramids with their bases glued together). Draw a planar graph representation of an octahedron. How many vertices, edges and faces does an octahedron (and your graph) have?
- The traditional design of a soccer ball is in fact a (spherical projection of a) truncated icosahedron. This consists of 12 regular pentagons and 20 regular hexagons. No two pentagons are adjacent (so the edges of each pentagon are shared only by hexagons). How many vertices, edges, and faces does a truncated icosahedron have? Explain how you arrived at your answers. Bonus: draw the planar graph representation of the truncated icosahedron.
- Your “friend” claims that he has constructed a convex polyhedron out of 2 triangles, 2 squares, 6 pentagons and 5 octagons. Prove that your friend is lying. Hint: each vertex of a convex polyhedron must border at least three faces.
5
Prove Euler's formula using induction on the number of edges in the graph.
- Answer
-
Proof
Let \(P(n)\) be the statement, “every planar graph containing \(n\) edges satisfies \(v - n + f = 2\text{.}\)” We will show \(P(n)\) is true for all \(n \ge 0\text{.}\) Base case: there is only one graph with zero edges, namely a single isolated vertex. In this case \(v = 1\text{,}\) \(f = 1\) and \(e = 0\text{,}\) so Euler's formula holds. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 0\text{.}\) Now consider an arbitrary graph containing \(k+1\) edges (and \(v\) vertices and \(f\) faces). No matter what this graph looks like, we can remove a single edge to get a graph with \(k\) edges which we can apply the inductive hypothesis to. There are two possibilities. First, the edge we remove might be incident to a degree 1 vertex. In this case, also remove that vertex. The smaller graph will now satisfy \(v-1 - k + f = 2\) by the induction hypothesis (removing the edge and vertex did not reduce the number of faces). Adding the edge and vertex back gives \(v - (k+1) + f = 2\text{,}\) as required. The second case is that the edge we remove is incident to vertices of degree greater than one. In this case, removing the edge will keep the number of vertices the same but reduce the number of faces by one. So by the inductive hypothesis we will have \(v - k + f-1 = 2\text{.}\) Adding the edge back will give \(v - (k+1) + f = 2\) as needed. Therefore, by the principle of mathematical induction, Euler's formula holds for all planar graphs.
6
Prove Euler's formula using induction on the number of vertices in the graph.
7
Euler's formula (\(v - e + f = 2\)) holds for all connected planar graphs. What if a graph is not connected? Suppose a planar graph has two components. What is the value of \(v - e + f\) now? What if it has \(k\) components?
8
Prove that the Petersen graph (below) is not planar.
- Answer:
-
What is the length of the shortest cycle? (This quantity is usually called the girth of the graph.)
9
Prove that any planar graph with \(v\) vertices and \(e\) edges satisfies \(e \le 3v - 6\text{.}\)
- Answer
-
Proof
We know in any planar graph the number of faces \(f\) satisfies \(3f \le 2e\) since each face is bounded by at least three edges, but each edge borders two faces. Combine this with Euler's formula:
\begin{equation*} v - e + f = 2 \end{equation*} \begin{equation*} v - e + \frac{2e}{3} \ge 2 \end{equation*} \begin{equation*} 3v - e \ge 6 \end{equation*} \begin{equation*} 3v - 6 \ge e. \end{equation*}
10
Prove that any planar graph must have a vertex of degree 5 or less.
5.4: Coloring
1
What is the smallest number of colors you need to properly color the vertices of \(K_{4,5}\text{?}\) That is, find the chromatic number of the graph.
- Answer
-
2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.
2
Draw a graph with chromatic number 6 (i.e., which requires 6 colors to properly color the vertices). Could your graph be planar? Explain.
- Answer
-
For example, \(K_6\text{.}\) If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.
3
Find the chromatic number of each of the following graphs.
4
A group of 10 friends decides to head up to a cabin in the woods (where nothing could possibly go wrong). Unfortunately, a number of these friends have dated each other in the past, and things are still a little awkward. To get the cabin, they need to divide up into some number of cars, and no two people who dated should be in the same car.
-
What is the smallest number of cars you need if all the relationships were strictly heterosexual? Represent an example of such a situation with a graph. What kind of graph do you get?
-
Because a number of these friends dated there are also conflicts between friends of the same gender, listed below. Now what is the smallest number of conflict-free cars they could take to the cabin?
Friend A B C D E F G H I J Conflicts with BEJ ADG HJ BF AI DJ B CI EHJ ACFI -
What do these questions have to do with coloring?
5
What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?
- Answer
-
The cube can be represented as a planar graph and colored with two colors as follows:
Since it would be impossible to color the vertices with a single color, we see that the cube has chromatic number 2 (it is bipartite).
6
Prove the chromatic number of any tree is two. Recall, a tree is a connected graph with no cycles.
- Describe a procedure to color the tree below.
- The chromatic number of \(C_n\) is two when \(n\) is even. What goes wrong when \(n\) is odd?
- Prove that your procedure from part (a) always works for any tree.
- Now, prove using induction that every tree has chromatic number 2.
7
Prove the 6-color theorem: every planar graph has chromatic number 6 or less. Do not assume the 4-color theorem (whose proof is MUCH harder), but you may assume the fact that every planar graph contains a vertex of degree at most 5.
8
Not all graphs are perfect. Give an example of a graph with chromatic number 4 that does not contain a copy of \(K_4\text{.}\) That is, there should be no 4 vertices all pairwise adjacent.
- Answer
-
The wheel graph below has this property. The outside of the wheel forms an odd cycle, so requires 3 colors, the center of the wheel must be different than all the outside vertices.
9
Prove by induction on vertices that any graph \(G\) which contains at least one vertex of degree less than \(\Delta(G)\) (the maximal degree of all vertices in \(G\)) has chromatic number at most \(\Delta(G)\text{.}\)
10
You have a set of magnetic alphabet letters (one of each of the 26 letters in the alphabet) that you need to put into boxes. For obvious reasons, you don't want to put two consecutive letters in the same box. What is the fewest number of boxes you need (assuming the boxes are able to hold as many letters as they need to)?
- Answer
-
If we drew a graph with each letter representing a vertex, and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, \(D\) would be adjacent to both \(C\) and \(E\)). By Brooks' theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.
11
Prove that if you color every edge of \(K_6\) either red or blue, you are guaranteed a monochromatic triangle (that is, an all red or an all blue triangle).
5.5: Euler Paths and Circuits
1
You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: you must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?
2
Which of the following graphs contain an Euler path? Which contain an Euler circuit?
- \(K_4\)
- \(K_5\text{.}\)
- \(K_{5,7}\)
- \(K_{2,7}\)
- \(C_7\)
- \(P_7\)
3
Edward A. Mouse has just finished his brand new house. The floor plan is shown below:
- Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.
- Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.
- After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.
4
For which \(n\) does the graph \(K_n\) contain an Euler circuit? Explain.
- Answer
-
When \(n\) is odd, \(K_n\) contains an Euler circuit. This is because every vertex has degree \(n-1\text{,}\) so an odd \(n\) results in all degrees being even.
5
For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain an Euler path? An Euler circuit? Explain.
- Answer
-
If both \(m\) and \(n\) are even, then \(K_{m,n}\) has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then there is an Euler path but not an Euler circuit.
6
For which \(n\) does \(K_n\) contain a Hamilton path? A Hamilton cycle? Explain.
- Answer
-
All values of \(n\text{.}\) In particular, \(K_n\) contains \(C_n\) as a subgroup, which is a cycle that includes every vertex.
7
For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain a Hamilton path? A Hamilton cycle? Explain.
- Answer
-
As long as \(|m-n| \le 1\text{,}\) the graph \(K_{m,n}\) will have a Hamilton path. To have a Hamilton cycle, we must have \(m=n\text{.}\)
8
A bridge builder has come to Königsberg and would like to add bridges so that it is possible to travel over every bridge exactly once. How many bridges must be built?
- Answer
-
If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit.
9
Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with paths?
- Answer
-
We are looking for a Hamiltonian cycle, and this graph does have one:
10
- Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.
- Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.
11
Consider the following graph:
- Find a Hamilton path. Can your path be extended to a Hamilton cycle?
- Is the graph bipartite? If so, how many vertices are in each “part”?
- Use your answer to part (b) to prove that the graph has no Hamilton cycle.
- Suppose you have a bipartite graph \(G\) in which one part has at least two more vertices than the other. Prove that \(G\) does not have a Hamilton path.
5.6: Matching in Bipartite Graphs
1
Find a matching of the bipartite graphs below or explain why no matching exists.
- Answer
-
The first and third graphs have a matching, shown in bold (there are other matchings as well). The middle graph does not have a matching. If you look at the three circled vertices, you see that they only have two neighbors, which violates the matching condition \(\card{N(S)} \ge \card{S}\) (the three circled vertices form the set \(S\)).
2
A bipartite graph that doesn't have a matching might still have a partial matching. By this we mean a set of edges for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph.
Your “friend” claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct?
3
One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge not in the matching, then it is called an augmenting path.
- Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?
- Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph?
4
The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this:
The question: how many different acceptable marriage arrangements which marry off all 20 children are possible?
- How many marriage arrangements are possible if we insist that there are exactly 6 boys marry girls not their own age?
- Could you generalize the previous answer to arrive at the total number of marriage arrangements?
- How do you know you are correct? Try counting in a different way. Look at smaller family sizes and get a sequence.
- Can you give a recurrence relation that fits the problem?
5
We say that a set of vertices \(A \subseteq V\) is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the edges). Since \(V\) itself is a vertex cover, every graph has a vertex cover. The interesting question is about finding a minimal vertex cover, one that uses the fewest possible number of vertices.
- Suppose you had a matching of a graph. How can you use that to get a minimal vertex cover? Will your method always work?
- Suppose you had a minimal vertex cover for a graph. How can you use that to get a partial matching? Will your method always work?
- What is the relationship between the size of the minimal vertex cover and the size of the maximal partial matching in a graph?
6
For many applications of matchings, it makes sense to use bipartite graphs. You might wonder, however, whether there is a way to find matchings in graphs in general.
- For which \(n\) does the complete graph \(K_n\) have a matching?
- Prove that if a graph has a matching, then \(\card{V}\) is even.
- Is the converse true? That is, do all graphs with \(\card{V}\) even have a matching?
- What if we also require the matching condition? Prove or disprove: If a graph with an even number of vertices satisfies \(\card{N(S)} \ge \card{S}\) for all \(S \subseteq V\text{,}\) then the graph has a matching.
5.7: Weighted Graphs and Dijkstra's Algorithm
1
Find a big-O estimate for the number of operations (additions and comparisons) used by Dijkstra's algorithm.
2
An oil well is located on the left side of the graph below; each other vertex is a storage facility. The edges represent pipes between the well and storage facilities or between two storage facilities. The weights on the edges represent the time it takes for oil to travel from one vertex to another. Using Dijkstra's algorithm find a shortest path and the total time it takes oil to get from the well to the facility on the right side. Use a table.
3
Solve the same problem as in #2, but draw several copies of the graph rather than the table when performing Dijkstra's algorithm.
4
A graph \(G\) is given by \(G=(\{v_1,v_2,v_3,v_4,v_5,v_6\},\{\{v_1,v_2\},\{v_1,v_3\},\{v_2,v_4\},\{v_2,v_5\},\{v_3,v_4\},\{v_4,v_5\},\{v_4,v_6\},\{v_5,v_6\}\})\). Furthermore, the weight on an edge is \(w(v_i,v_j)=|i-j|\). Draw the graph, determine a shortest path from \(v_1\) to \(v_6\), and also give the total weight of this path. Use Dijkstra's algorithm (you may make a table or draw multiple copies of the graph).
5.8: Trees
1
Which of the following graphs are trees?
a. \(G=(V,E)\) with \(V=\{a,b,c,d,e\}\) and \(E=\{\{a,b\},\{a,e\},\{b,c\},\{c,d\},\{d,e\}\}\)
b. \(G=(V,E)\) with \(V=\{a,b,c,d,e\}\) and \(E=\{\{a,b\},\{b,c\},\{c,d\},\{d,e\}\}\)
c. \(G=(V,E)\) with \(V=\{a,b,c,d,e\}\) and \(E=\{\{a,b\},\{a,c\},\{a,d\},\{a,e\}\}\)
d. \(G=(V,E)\) with \(V=\{a,b,c,d,e\}\) and \(E=\{\{a,b\},\{a,c\},\{d,e\}\}\)
2
For each degree sequence below, decide whether it must always, must never, or could possibly be a degree sequence for a tree. Remember, a degree sequence lists out the degrees (number of edges incident to the vertex) of all the vertices in a graph in non-increasing order.
a. (4,1,1,1,1)
b. (3,3,2,1,1)
c. (2,2,2,1,1)
d. (4,4,3,3,3,2,2,1,1,1,1,1,1,1)
3
For each degree sequence below, decide whether it must always, must never, or could possibly be a degree sequence for a tree. Justify your answers.
a. (3,3,2,2,2)
b. (3,2,2,1,1,1)
c. (3,3,3,1,1,1)
d. (4,4,1,1,1,1,1,1)
4
Suppose you have a graph with \(v\) vertices and \(e\) edges that satisfies \(v=e+1.\) Must the graph be a tree? Prove your answer.
5
Prove that any graph (not necessarily a tree) with \(v\) vertices and \(e\) edges that satisfies \(v>e+1\) will NOT be connected. [Hint: try a proof by contradiction and consider a spanning tree of the graph.]
6
If a graph \(G\) with \(v\) vertices and \(e\) edges is connected and has \(v<e+1\) must it contain a cycle? Prove your answer. [Hint: use the contrapositive.]
7
We define a forest to be a graph with no cycles.
a. Explain why this is a good name. That is, explain why a forest is a union of trees.
b. Suppose \(F\) is a forest consisting of \(m\) trees and \(v\) vertices. How many edges does \(F\) have? Explain.
c. Prove that any graph \(G\) with \(v\) vertices and \(e\) edges that satisfies \(v<e+1\) must contain a cycle (i.e., not be a forest).
8
Give a proof of the following statement: A graph is a forest if and only if there is at most one path between any pair of vertices. Use proof by contrapositive (and not a proof by contradiction) for both directions.
9
Give a careful proof by induction on the number of vertices, that every tree is bipartite.
10
a. Suppose we designate vertex \(e\) as the root. List the children, parents and siblings of each vertex. Does any vertex other than \(e\) have grandchildren?
b. Suppose \(e\) is not chosen as the root. Does our choice of root vertex change the number of children \(e\) has? The number of grandchildren? How many are there of each?
c. In fact, pick any vertex in the tree and suppose it is not the root. Explain why the number of children of that vertex does not depend on which other vertex is the root.
d. Does the previous part work for other trees? Give an example of a different tree for which it holds. Then either prove that it always holds or give an example of a tree for which it doesn't.
11
Let T be a rooted tree that contains vertices \(u\), \(v\), and \(w\) (among possibly others). Prove that if \(w\) is a descendant of both \(u\) and \(v\), then \(u\) is a descendant of \(v\) or \(v\) is a descendant of \(u\).
12
Unless it is already a tree, a given graph \(G\) will have multiple spanning trees. How similar or different must these be?
a. Must all spanning trees of a given graph be isomorphic to each other? Explain why or give a counterexample.
b. Must all spanning trees of a given graph have the same number of edges? Explain why or give a counterexample.
c. Must all spanning trees of a graph have the same number of leaves (vertices of degree 1)? Explain why or give a counterexample.
13
Find all spanning trees of the graph below. How many different spanning trees are there? How many different spanning trees are there up to isomorphism(that is, if you grouped all the spanning trees by which are isomorphic, how many groups would you have)?
14
Give an example of a graph that has exactly 7 different spanning trees. Note, it acceptable for some or all of these spanning trees to be isomorphic. [Hint: there is an example with 7 edges.)
15
Prove that every connected graph which is not itself a tree must have at last three different (although possibly isomorphic) spanning trees.
16
Consider edges that must be in every spanning tree of a graph. Must every graph have such an edge? Give an example of a graph that has exactly one such edge.
17
An \(m\)-ary tree is a rooted tree in which every internal vertex has at most \(m\) children. A full \(m\)-ary tree is a rooted tree in which every internal vertex has exactly \(m\) children. A full \(m\)-ary tree with \(n\) vertices has how many internal vertices and how many leaves?
5.9.1: Tree traversal
1
Create a rooted ordered tree for the expression \((4+2)^3/((4-1)+(2*3))+4\).
2
Determine the preorder and postorder traversals of this tree.
3
Evaluate the following postfix expression: \(6\,2\,3\,-\,+\,2\,3\,1\,*\,+\,-\).
Evaluate the following prefix expression: \(\uparrow\,-\,*\,3\,3\,*\,1\,2\,3\).
4
Find a big-O estimate of the time complexity of the preorder, inorder, and postorder traversals.
5.9.2: Spanning tree algorithms
Use the graph below for all 5.9.2 exercises.
1
Use the depth-first search algorithm to find a spanning tree for the graph above. Let \(v_1\) be the vertex labeled "Tiptree" and choose adjacent vertices alphabetically. You can ignore the edge weights.
2
Use the breadth-first search algorithm to find a spanning tree for the graph above, with Tiptree being \(v_1\). Add vertices to \(L\) alphabetically.
3
Find a minimum spanning tree using Prim's algorithm. Make sure to keep track of the order in which edges are added to the tree. Then find a minimum spanning tree using Kruskal's algorithm, again keeping track of the order in which edges are added.
4
Find a shortest path spanning tree from Maldon. Make sure to show steps of Dijkstra's algorithm in detail.
5.9.3: Transportation Networks and Flows
1
A telephone call can be routed from South Bend to Orlando on various routes. The line from South Bend to Indianapolis can carry 40 calls at the same time. Other lines and their capacities are as follows: South Bend to St. Louis (30 calls), South Bend to Memphis (20 calls), Indianapolis to Memphis (15 calls), Indianapolis to Lexington (25 calls), St. Louis to Little Rock (20 calls), Little Rock to Memphis (15 calls), Little Rock to Orlando (10 calls), Memphis to Orlando (25 calls), Lexington to Orlando (15 calls). Draw a transportation network displaying this information.
2
Fill in the missing values on the edges so that the result is a flow on the transportation network.
3
Use the max flow algorithm to find a maximal flow and minimum cut on the transportation network below. Determine the value of the flow. Find a minimal cut and give its capacity.
4
Use the max flow algorithm to find a larger flow than the one currently displayed on the transportation network below.
5
Use the max flow algorithm to find a larger flow than the one currently displayed on the transportation network below.