Math 485, Graph Theory: Homework #4

Stephen G. Simpson

Due Friday, December 4, 2009

The assignment consists of Exercises 3.1.8, 3.1.19, 3.1.24, 3.1.25, 3.2.6, 6.1.12, 6.1.25, 6.1.35, 6.2.6 in the West textbook. Each exercise counts for 10 points. Here are some (rather sketchy) solutions.

3.1.8. Let T be a tree. If M and M′ are perfect matchings in T, consider the symmetric difference MΔM′. Since M and M′ are matchings, every component of MΔM′ is an even cycle or a path P which alternates between edges in M and edges in M′. Since T is a tree, there are no cycles. Since M and M′ are perfect matchings, the last edge of P cannot belong to M′ or to M. We conclude that MΔM′ has no edges, i.e., M = M′. We have proved that a tree has at most one perfect matching.

Here is an alternative proof. We proceed by induction on the number of vertices in T. Let u be a leaf of T, let v be the vertex adjacent to u, let v_{1}, …, v_{k} be the vertices other than u which are adjacent to v, and for i = 1, …, k let T_{i} be the component of T − u, v which contains v_{i}. If M is a perfect matching in T, then necessarily uv ∈ M, hence vv_{i} ∉ M, hence M_{i} = M ∩ T_{i} is a perfect matching in T_{i}. By inductive hypothesis, M_{i} is the only perfect matching in T_{i}. From this it follows that M is the only perfect matching in T.

3.1.19. Let A_{1}, …, A_{m} be a family of finite sets. Consider the bipartite graph G = (X, Y) with X = {1, …, m} and Y = ⋃_{i=1}^{m} A_{i} such that i is adjacent to a if and only if a ∈ A_{i}. Hall’s Theorem applied to G says: G has an X-saturated matching if and only if |N(S)| ≥ |S| for all S ⊆ X. In other words, A_{1}, …, A_{m} has a system of distinct representatives if and only if | ⋃_{i∈S} A_{i}| ≥ |S| for all S ⊆ {1, …, m}.

3.1.24. Let A = (a_{ij}) be an n × n matrix with nonnegative integer entries.

First assume that A is the sum of k permutation matrices. Then each permutation matrix contributes 1 to each row and column sum of A. Hence, each row and column sum of A is equal to k.

Conversely, assume that each row and column sums of A is equal to k. Consider the bipartite graph G with vertices x_{1}, …, x_{n}, y_{1}, …, y_{n} containing a_{ij}-many edges from x_{i} to y_{j}. Clearly G is k-regular. Hence by the Marriage Theorem we can find a perfect matching M in G. Consider the n × n permutation matrix P = (p_{ij}) where p_{ij} = 1 if x_{i}y_{j} ∈ M, 0 otherwise. Then each row and column sum of A − P is equal to k − 1. By induction on k we may assume that A−P is the sum of k −1 permutation matrices. Thus A is the sum of k permutation matrices.

3.1.25. Let P = (p_{ij}) be an n × n doubly stochastic matrix. Thus each p_{ij} is ≥ 0, and each row and column sum is equal to 1. We shall prove that P is a convex combination of permutation matrices. Consider the simple bipartite graph G with vertices x_{1}, …, x_{n}, y_{1}, …, y_{n} and with x_{i} adjacent to y_{j} if and only if p_{ij} > 0. Since P is doubly stochastic, the sum of all the entries of P is n. Hence, the minimum number of rows and columns which contain all of the nonzero entries of P is n. In other words, the minimum size of a vertex covering of G is n. Hence, by the König/Egerváry Theorem, G contains a perfect matching. In other words, P contains n nonzero entries no two of which lie in the same row or column. Let P_{1} be the permutation matrix with 1 in place of each of these n entries. Let c_{1} be the minimum of these entries, and let Q = (P − c_{1}P_{1})/(1 − c_{1}). Then Q is again a doubly stochastic matrix, and Q has fewer nonzero entries than P. By induction on the number of nonzero entries, we may assume that Q is a convex combination of permutation matrices. It follows that P = c_{1}P_{1} + (1 − c_{1})Q is again a convex combination of permutation matrices. This completes the proof.

3.2.6. Let A be the given 5 × 5 matrix. We wish to find a minimum-weight transversal of A. It suffices to find a maximum-weight transversal of −A. So apply the Hungarian algorithm exactly as in the textbook, but to −A instead of A. In this way we get

4 0 0 0 0
0 0 5 0 0
0 5 0 0 0
0 0 0 0 7
0 0 0 9 0

as a minimum-weight transversal of A.

6.1.12. Draw the five regular polyhedra as planar graphs. Show that the octahedron is the dual of the cube, and the icosahedron is the dual of the dodecahedron. The discussion in Application 6.1.28 of the textbook shows that the octahedron is the dual of the cube, and the icosahedron is the dual of the dodecahedron. The drawings are left to the student.

6.1.25. Let G be a self-dual planar graph on n vertices. Euler’s Formula says n − e + f = 2, but since G is self-dual we also have n = f. Hence n − e + n = 2, i.e., e = 2n − 2. An example of such a graph is the (n − 1)-wheel.

6.1.35. Let G be a simple planar graph with at least four vertices. By adding edges we may assume that G is a triangulation (see Definition 6.1.25 and Proposition 6.1.26). It follows that e = 3n − 6 and, moreover, each vertex is of degree d_{i} ≥ 3. By the degree-sum formula we have ∑_{i=1}^{n} d_{i} = 2e = 6n − 12, i.e., ∑_{i=1}^{n}(6 − d_{i}) = 12. Since d_{i} ≥ 3 it follows that 6 − d_{i} ≤ 3, hence there must be at least four vertices with 6 − d_{i} > 0, i.e., d_{i} < 6.

For each even number n ≥ 4 we can construct a simple planar graph with exactly n vertices, only four of them of degree < 6. Namely, start with the n/2-ladder and add edges until the four corners of the n/2-ladder are of degree 3 and the remaining vertices are of degree 6.

6.2.6. We are to prove Fáry’s Theorem: Every simple planar graph has a straightline embedding.

Let G be a simple planar graph on n vertices. By adding edges (see Definition 6.1.25 and Proposition 6.1.26) we may safely assume that G is a triangulation. We shall prove that for each triangle abc in G we can find a straight-line planar representation of G which has abc as the outer face. We prove this by induction on n. We may safely assume that n ≥ 4. By Exercise 6.1.35 G has at least four vertices of degree ≤ 5, so let v be a vertex of degree ≤ 5 other than a, b, c. Let G′ be a triangulation of G − v. Applying the inductive hypothesis to G′, we find a straight-line planar representation of G − v with abc as the outer face. In this representation of G − v, the vertices of G which were adjacent to v form a face of degree ≤ 5, i.e., a polygon P with ≤ 5 edges. Select a point p inside P which can “see” all of the vertices of P. In other words, P contains straight lines from p to the vertices of P. Adding these lines to our straight-line representation of G−v, we obtain a straight-line representation of G. This completes the proof.