Skip to main content
\(\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}}\)
[ "article:topic", "transcluded:yes" ]
Mathematics LibreTexts

4.7: Graph Theory (Exercises)

  • Page ID
    15344
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \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

    ParseError: EOF expected (click for details)
    Callstack:
        at (Template:MathJaxLevin), /content/body/div/p[1]/span, line 1, column 11
        at template()
        at (Bookshelves/Combinatorics_and_Discrete_Mathematics/Book:_Discrete_Mathematics_(Levin)/4:_Graph_Theory/4.E:_Graph_Theory_(Exercises)), /content/body/span, line 1, column 22
        at wiki.page()
        at (Courses/Saint_Mary's_College,_Notre_Dame,_IN/SMC:_MATH_339_-_Discrete_Mathematics_(Rohatgi)/Text/4:_Graph_Theory/4.7:_Graph_Theory_(Exercises)), /content/body/div/pre, line 2, column 10
    
    \)
    \( \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}{&}\)

    4.1: 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).

    image-88.svg     image-89.svg

    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:

    image-90.svg

    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\}\}\)
    1. 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.

    2. Define a new function \(g\) (with \(g\not=f\)) that defines an isomorphism between Graph 1 and Graph 2.

    3. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.

    image-91.svg

    6

    Which of the graphs below are bipartite? Justify your answers.

    image-92.svg  image-93.svg   image-94.svg   image-95.svg

    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:

    image-96.svg    image-97.svg   image-98.svg

    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.

    1. Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles.
    2. Two different graphs with 8 vertices all of degree 2.
    3. Two different graphs with 5 vertices all of degree 4.
    4. Two different graphs with 5 vertices all of degree 3.
    Answer
    1. For example:

    image-99.svg    image-100.svg

    1. 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.
    2. 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{.}\)
    3. 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).

    4.2: Planar Graphs

    1

    Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces? Explain.

    Answer

    No. A (connected) planar graph must satisfy Euler's formula: \(v - e + f = 2\text{.}\) Here \(v - e + f = 6 - 10 + 5 = 1\text{.}\)

    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.

    Answer

    \(G\) has 10 edges, since \(10 = \frac{2+2+3+4+4+5}{2}\text{.}\) It could be planar, and then it would have 6 faces, using Euler's formula: \(6-10+f = 2\) means \(f = 6\text{.}\) To make sure that it is actually planar though, we would need to draw a graph with those vertex degrees without edges crossing. This can be done by trial and error (and is possible).

    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.

    1. 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?
    2. 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.
    3. 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.

    image-111.svg

    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.

    4.3: 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.

    image-121.svg   image-122.svg   image-123.svg   image-124.svg   image-125.svg

    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.

    Answer

    The chromatic numbers are 2, 3, 4, 5, and 3 respectively from left to right.

    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.

    1. 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?

    2. 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
    3. 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?

    image-126.svg

    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.

    1. image-127.svg
    1. Describe a procedure to color the tree below.
    2. The chromatic number of \(C_n\) is two when \(n\) is even. What goes wrong when \(n\) is odd?
    3. Prove that your procedure from part (a) always works for any tree.
    4. 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.

    image-128.svg

    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).

    4.4: 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?

    image-139.svg

    Answer

    This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

    2

    Which of the following graphs contain an Euler path? Which contain an Euler circuit?

    1. \(K_4\)
    2. \(K_5\text{.}\)
    3. \(K_{5,7}\)
    4. \(K_{2,7}\)
    5. \(C_7\)
    6. \(P_7\)
    Answer
    1. \(K_4\) does not have an Euler path or circuit.
    2. \(K_5\) has an Euler circuit (so also an Euler path).
    3. \(K_{5,7}\) does not have an Euler path or circuit.
    4. \(K_{2,7}\) has an Euler path but not an Euler circuit.
    5. \(C_7\) has an Euler circuit (it is a circuit graph!)
    6. \(P_7\) has an Euler path but no Euler circuit.

    3

    Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

    image-140.svg

    1. 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.
    2. Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.
    3. 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

    Add texts here. Do not delete this text first.

    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.

    image-141.svg

    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?image-142.svg

    Answer

    We are looking for a Hamiltonian cycle, and this graph does have one:

    image-143.svg

    10

    1. 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.
    2. 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:

    image-144.svg

    1. Find a Hamilton path. Can your path be extended to a Hamilton cycle?
    2. Is the graph bipartite? If so, how many vertices are in each “part”?
    3. Use your answer to part (b) to prove that the graph has no Hamilton cycle.
    4. 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.

    4.5: Matching in Bipartite Graphs

    1

    Find a matching of the bipartite graphs below or explain why no matching exists.

    image-146.svg   image-147.svg   image-148.svg

    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\)).

    image-149.svg   image-150.svg   image-151.svg

    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?

    image-152.svg

    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.

    1.  
    1. 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?

    image-153.svg

    1. 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?

    ​​​​​​​image-154.svg

    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:

    image-155.svg

    The question: how many different acceptable marriage arrangements which marry off all 20 children are possible?

    1. How many marriage arrangements are possible if we insist that there are exactly 6 boys marry girls not their own age?
    2. Could you generalize the previous answer to arrive at the total number of marriage arrangements?
    3. How do you know you are correct? Try counting in a different way. Look at smaller family sizes and get a sequence.
    4. 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.

    1. Suppose you had a matching of a graph. How can you use that to get a minimal vertex cover? Will your method always work?
    2. 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?
    3. 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.

    1. For which \(n\) does the complete graph \(K_n\) have a matching?
    2. Prove that if a graph has a matching, then \(\card{V}\) is even.
    3. Is the converse true? That is, do all graphs with \(\card{V}\) even have a matching?
    4. 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.