Math 316/416Problem Set II -- Solutions 15 March 2001

1. Supplement II, #22.
2. Supplement II, #32.
3. 2.2 #14
4. 2.4 #10
5. 3.3 #24

Solutions

1. Let each edge of a complete graph on 6 vertices be painted red or white. Show that there must always be either a red triangle of 3 edges or a white triangle of 3 edges.

   Solution: Pick one vertex, and call it A. It has degree 5. Of the 5 edges incident to A, at least three must be the same color, say white (covers both cases by switching the colors). Name these three edges (A, B),(A, C), and (A, D). If any of the edges (B, C),(C, D), or (D, B) is white, then the graph has a white triangle using this white edge and the edges incident to A. If all three are red, then the triangle B, C, D is a red triangle.

   

2. (a) Show that there is no way to pair off the 14 vertices in the graph below with 7 edges.
   1. Generalize part (a) to the problem of trying to use 31 dominoes to cover the 62 squares of an 8 x 8 chessboard with two opposite corner squares removed.

   Solution: (a) Several methods possible: One is: Choose one of the vertices of degree two, call it A, and try to create a pairing. Since A must be included in the pairing, there are only two choices for the edge which includes A. Either choice forces other edges to be included in the pairing leading to two non-adjacent vertices remaining. So the pairing isn't possible. See the example, with the edges that are forced by the choice of edge 1 below, numbered in order.

   

   Second method: The graph is bipartite, with unequal sized classes. Since each edge pairs up a vertex in one class with one in the other class, it is impossible to pair up all 14 vertices.

   1. First idea: Each domino covers one red and one black square. There are unequal numbers of the colors, so the covering is impossible. Second idea: Model the problem with a graph -- 8 x 8 vertices, corners removed -- and note that it's bipartite, with unequal numbers of vertices in the classes.
3. Suppose a classroom has 25 students seated in desks in a square 5 x 5 array. The teacher wants to alter the seating by having every student move to an adjacent seat (just ahead, just behind, on the left, or on the right). Show that such a move is impossible.

   Solution: Model the situation with a graph consisting of 25 vertices arranged in a 5 x 5 array (representing the desks), with edges representing possible moves. The problem is asking to divide the vertices up into disjoint circuits in this graph. However, the graph is bipartite, and Theorem 2 (page 31) then says that every circuit in the graph has even length. Since every circuit uses an even number of vertices, there is no way to use all 25 vertices in disjoint circuits (the sum of even numbers is an even number).

4. Show that if every region in a planar graph has an even number of bounding edges, then the vertices can be 2-colored.

   Solution: 2-colorable is the same as bipartite, and Theorem 2 on page 31 tells us that a graph is bipartite if and only if all circuits have even length. So if we can show that all circuits in our graph G have even length, we will be done. Assume every region in a planar graph G has an even number of bounding edges. Let H be a circuit in G, of length | H|.

   Two approaches: First: Consider the regions inside H, of degrees r₁, r₂,..., r_k. Each of the r_i is even by hypothesis. Let us count the sum r₁ + r₂ + ... + r_k in a different way: First, count the edges of H; there are | H| of them. Now each edge that is completely inside H bounds two of the regions inside H, and so must be counted twice in r₁ + r₂ + ... + r_k. If there are m edges completely inside H, this yields

   r₁ + r₂ + ... + r_k = | H| + 2m $$\Rightarrow$$| H| = r₁ + r₂ + ... + r_k - 2m.

   Since each summand on the right-hand side of the last equation is even, | H| must be even.

   Second: Use induction on the number of regions enclosed by H. If H only encloses one region, then | H| is even by hypothesis. So assume any circuit bounding k - 1 $\geq$1 regions has even length. Assume there are k regions inside H. Consider a region R which shares at least one edge with H. Create a new circuit H' which shares all edges with H except that it uses all edges of R that H doesn't use, and doesn't use the edges of R that H uses. Then R is on the outside of H', and H' has k - 1 regions inside it. By the inductive hypothesis, H' has even length. Finally, let r be the number of edges of R used by H, and let r' be the number of edges of R used by H'. Then r + r' is the number of bounding edges of R, which is even by assumption; therefore r - r' is even also; and so | H| = | H'| + r - r' is even.

5. Prove that Kruskal's algorithm gives a minimal spanning tree.

   Solution: Let G be a graph, and consider a spanning tree K of G created by Kruskal's algorithm. Among all minimal spanning trees of G (we don't know K is minimal; that's what we're trying to prove), consider one which has as many edges as possible in common with K; call it M. If M = K, then K is minimal and we're done.

   If K $\neq$M, then let e_k = (a, b) be the first edge chosen in the creation of K which is not in M. Then in M there must be some other path between a and b (since M is a spanning tree). Along this other path, there must be some edge e^* = (c, d ) which is not in K, or else K would contain a circuit (since K contains the edge (a, b)). Now compare the weights on the two edges e_k and e^*. If e^* has a lower weight, then Kruskal's algorithm would have chosen e^* instead of e_k at the kth step; if e_k has a lower weight, then we could replace e^* in M with e_k and have a spanning tree with smaller total weight, contradicting minimality of M; finally, if the two have the same weight, then we could replace e^* in M with e_k and have a minimal spanning tree with more edges in common with K than M has, contradicting the assumption that M has as many edges as possible in common with K.

• About this document ...