You$must$attach$this$cover$page$to$the$front$of$your$HW$or$you$will$lose$5$points.$ $ $ APMA$1860$Homework$2$ $ $ First$Name:$____________________________$$$Last$Name:$______________________________$ $ $ Problems$ Value$ Score$ 1$ 10$ $ 2$ 10$ $ 3$ 14$ $ 4$ 14$ $ 5$ 12$ $ 6$ 10$ $ 7$ 10$ $ 8$ 10$ $ 9$ 10$ $ Total$ 100$ $ *$Outside$sources$and$collaborators:$ $ APMA 1860 : Homework 2 Required problems. 1. Let G be a connected graph on n vertices with n 1 edges. Prove that G is a tree. 2. A spanning subgraph G0 of a graph G is a subgraph of G with V (G0 ) = V (G). In other words, it is a subgraph that includes all of the vertices. A spanning tree is a spanning subgraph that is also a tree. (a) Prove that every connected graph has a spanning tree. (Hint: There are two common ways to prove this: start with a graph and remove edges appropriately until you get a spanning tree, or start with no edges and add them appropriately until you get a spanning tree.) (b) Prove that a graph is connected if and only if it has a spanning tree. 3. Prufer Encoding. Prufer encoding is a process that maps (labeled) trees on n 3 vertices V = {1, . . . , n} into (n 2)-length sequences of integers taken from the set V . This problem takes you through Prufer encoding. (a) First, we will define a mapping b(T ) that takes a tree T into a number and a mapping S(T ) that takes a tree T into another tree on a smaller vertex set. Fix 2 k n. Let T be a tree on k vertices chosen from the set {1, . . . , n}. Of all vertices in T with degree one, let a(T ) be the smallest vertex (meaning the vertex whose label is the smallest number), let b(T ) be the unique vertex that is adjacent to a(T ), and let S(T ) be the tree created by deleting a(T ) from T . i. ii. iii. iv. Prove that a(T ) is well-defined, namely, that there always exists a smallest vertex with degree 1. Prove that b(T ) is well-defined, namely, that there is a unique vertex adjacent to a(T ). Prove that S(T ) is a tree. For 0 j < k, define S j (T ) to be the tree created by j applications of S to T . So S 0 (T ) = T , S 1 (T ) = S(T ), S 2 (T ) = S(S(T )), S 3 (T ) = S(S(S(T ))), and so on. Prove that S j (T ) is a tree. Write a function (in the language of your choice) that inputs a tree T and outputs b(T ) and S(T ).1 (b) Now we will define Prufer encoding of a tree. Let T be a tree on V = {1, . . . , n} for n 3. The Prufer encoding of T is the sequence (T ) = (b(T ), b(S(T )), b(S 2 (T )), . . . , b(S n 3 (T ))). i. Prove that (T ) is well-defined and that (T ) 2 {1, . . . , n}n quences taken from the set {1, . . . , n}. 1 2, meaning (n 2)-length se- It's probably easiest to have the function input a graph and then complain if the minimal degree is not 1. Checking that the graph is a tree is not necessary. It can be helpful to have the function output a(T ), also, so that it is easier to check your code. Here are some suggestions for how to use Matlab's graph functions to this problem. Matlab's graph object keeps internal, numerical labels for the vertices, which are always 1, . . . , |V |, and also user-defined labels, which should be character strings. Sometimes it's fine to use Matlab's internal labels, but in this problem, where you want the labels to be subsets of 1, . . . , n and where you want the labels to stay the same as you add and remove vertices, then it's best to use your own labels. If s and t are m-length vectors with {s(k), t(k)} giving the kth edge taken from the vertex set V = {1, . . . , n}, then you can create the graph in Matlab with G=graph(s,t,,strtrim(cellstr(num2str((1:n)')))). The vertices will be labeled with character strings corresponding to their numerical label. Now, suppose you have a graph like this, then you can get the numerical values of vertex labels with V=str2double(table2cell(G.Nodes)). You can get the degree sequence (corresponding to this ordering of the vertices) with d=degree(G), so a=min(V(d==1)) finds the smallest vertex of degree one in G and aL=num2str(a) gets its label. You can find the numerical values of labels of vertices adjacent to vertex a with b=str2double(neighbors(G,aL)) and you can remove vertices a from G with H=rmnode(G,aL). H is a new graph object with the vertices in b deleted from G. Note that you are always telling Matlab about a vertex by using it's character string. If you tell Matlab about a vertex using a number, then it will think you are talking about its internal ordering of the vertices, which is not what you want in this problem. Typing help graph in Matlab will show you all of Matlab's graph functions. 1 ii. Let cv ( ) be the number of times that vertex v appears in the sequence = (T ). Prove that cv ( ) = dv 1, where dv is the degree of v in T . Write a function that computes the Prufer encoding of a tree on at least 3 vertices. 4. Prufer Decoding. Now we will reverse the process of Prufer encoding. You might think that we would work backwards, but we are going to start at the beginning and reconstruct the tree T in the order that it was deconstructed. Let = (T ), so that = ( 1 , . . . , n 2 ). We get n from the length of (plus two) (0) (0) and we get the degree sequence of T from as described above. Let d(0) = (d1 , . . . , dn ) be the degree sequence of T . Let G(0) be the empty graph on V = {1, . . . , n}. (a) Find the minimum vertex v 2 V that has degree 1 in d(0) . Explain why v = a(T ) and why the edge e = {v, 1 } is in T . (0) (b) Add the edge e to G(0) to get G(1) and subtract one from each of dv and d sequence d(1) . Explain why (1) du (0) 1 to get a new degree is the degree of u in S(T ) for any vertex u of S(T ). (c) Now repeat these two steps: Find the minimum vertex v 2 V that has degree 1 in d(1) . Explain why v = a(S(T )) and why the edge e = {v, 2 } is in T . Add the edge e to G(1) to get G(2) and subtract (1) (1) (2) one from each of dv and d 2 to get a new degree sequence d(2) . Explain why du is the degree of u in S 2 (T ) for any vertex u of S 2 (T ). (d) Continue in this manner for n 2 steps until you get G(n 2) and d(n not in G(n 2) ? Add this edge to G(n 2) to get G. Why is G = T ? 2) . What edge is in T that is Write a function that constructs a tree T from its Prufer encoding (T ).2 Make sure to check your code by going back and forth between a tree and its Prufer code. (e) Prove that (T ) is injective, meaning that if T 6= T 0 , then (T ) 6= (T 0 ). (f) Prove that (T ) is surjective on U = {1, . . . , n}n 2 , meaning that for every 0 2 U there is some tree T with (T ) = 0 . (Hint. Assume there is a smallest n for which it is not surjective and derive a contradiction.) (g) Cayley's formula. Prove that there are nn nn 2 different spanning trees. 2 (labeled) trees on a set of n vertices. Prove that Kn has 5. Let X = (X1 , . . . , Xn 2 ) be a vector of iid Uniform{1, . . . , n} random variables3 , and let T be the unique tree on V = {1, . . . , n} with Prufer code (T ) = X. (a) Prove that T is a random tree selected uniformly from the set of all trees on V . (b) Generate 9 independent random trees on n = 10 vertices, plot them (in 9 separate figures on the same page4 ), and attach the plot to your homework solutions. 6. Let G be a planar graph with n vertices, m edges, and c connected components. Suppose it is embedded into the plane with r regions. (a) Prove that n m + r = 1 + c. 2 Here are some Matlab commands that I found useful. If b is a vector containing values in {1, . . . , n}, then d = histc(b,1:n) creates an n-length vector d such that d(k) counts how many times k occurs in b. G = graph(,,,strtrim(cellstr(num2str((1:n)')))) creates the empty graph on vertices {1, . . . , n} labeled with text strings. To add edge {u, v} to G, you can do G=addedge(G,num2str(u),num2str(v)). 3 You can generate X in Matlab with X=randi(n,1,n-2). 4 The subplot(3,3,k) function in Matlab is useful here. 2 (b) Consider two different planar embeddings of a planar graph G. (G is not necessarily connected.) Show that each embedding has the same number of regions. Hence, the number of regions of a planar graph is an intrinsic property of the graph, independent of how it is drawn. 7. Use Kuratowski's Theorem to prove Wagner's Theorem: A graph G is planar if and only if G has neither K5 nor K3,3 as a minor. 8. Prove that every planar graph has at least one vertex of degree 5 or less. 9. Graph coloring. A proper coloring of a graph is an assignment of colors to vertices so that adjacent vertices are different colors. A graph G is k-colorable if there is a proper coloring of G that uses at most k different colors. The smallest k for which a graph is k-colorable is called the chromatic number of the graph. (a) Prove that every graph on n vertices is n-colorable, and give an example (with explanation) of a graph on n vertices with chromatic number n. (b) Prove the Six-Color Theorem5 : Every planar graph is 6-colorable. (Hint: Use induction on the number of vertices, and consider how to color a vertex of degree 5 or less as guaranteed by problem 8.) Just for fun. Do not submit solutions. 10. Connect a to A, b to B, c to C, and d to D by edges (not necessarily straight) which are inside the rectangle and don't cross one another. A B C d D a c b 11. Find the error (and explain why it is an error) in the following \"proof\": Theorem. If A is a set of horses, then all the horses in A are the same color. Proof. For each n 1, define the statement Sn = If A is a set of n horses, then all the horses in A are the same color. S1 is clearly true. Assume that Sn is true for some n. We will now prove that Sn+1 has to be true. Let A be a set of n + 1 horses, labeled 1, . . . , n + 1. Remove horse 1. Horses 2, 3, . . . , n + 1 are a set of n horses, so they are all the same color, since we are assuming that Sn is true. Now, instead, remove horse 2. Again, horses 1, 3, 4, . . . , n + 1 are a set of n horses, so they are all the same color. Continue in this manner to argue that each subset of n horses selected from A must all be the same color. Obviously, then, all the horses in A must be the same color. Since A was an arbitrary set of n + 1 horses, the statement Sn+1 must be true. Hence, by the principle of induction, Sn is true for all n 1. 12. Returning to problem 5, generate many random trees on n vertices and study some property of the collection, such as the distribution of maximum degrees. How does it grow with n? 5 The Four-Color Theorem is one of the most famous theorems in graph theory, and it has a colorful history that is worth reading about. It says that every planar graph is 4-colorable. The Four-Color Theorem obviously implies the Six-Color Theorem, but you can't use the Four-Color Theorem in your proof. 3