Ch. 4: Trees

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 4.1. Bridges 4.2. Trees 4.3. The Minimum Spanning Tree Problem 4.4. Excursion: The Number of Spanning Trees

60 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

1. GGG is a graph and XXX is a set of edges of GGG . What is the graph G−XG - XG−X ?

   The graph with the same vertex set as GGG and all edges of GGG except those in XXX . For a single edge eee this is G−eG - eG−e . If GGG has order nnn , then G−E(G)G - E(G)G−E(G) is the empty graph K‾n\overline{K}_nKn​ .

2. When is an edge e=uve = uve=uv of a connected graph GGG a bridge?

   When G−eG - eG−e is disconnected. G−eG - eG−e then has exactly two components, one containing uuu and the other containing vvv .

3. When is an edge eee of a disconnected graph GGG a bridge? State it with k(G)k(G)k(G) , the number of components.

   When k(G−e)=k(G)+1k(G - e) = k(G) + 1k(G−e)=k(G)+1 , i.e. eee is a bridge of the component containing it. The four bridges (bold): u2u5u_2u_5u2​u5​ , v3v4v_3v_4v3​v4​ , v4v5v_4v_5v4​v5​ and w1w2w_1w_2w1​w2​ .

4. vvv is an end-vertex (degree 1) of a connected graph GGG . Is G−vG - vG−v connected?

   Yes. The edge eee at vvv is a bridge, and the component of G−eG - eG−e containing vvv is just vvv ; the other component is G−vG - vG−v .

5. Theorem 4.1 An edge eee of a graph GGG is a bridge if and only if … ?

   eee lies on no cycle of GGG .

6. An edge eee of a graph GGG is a bridge if and only if eee lies on no cycle of GGG .Why does an edge e=uve = uve=uv that is not a bridge lie on a cycle?

   G−eG - eG−e still has a uuu – vvv path PPP , and PPP together with eee forms a cycle. Work inside the component of GGG containing eee .

7. An edge eee of a graph GGG is a bridge if and only if eee lies on no cycle of GGG .Why is an edge e=uve = uve=uv on a cycle CCC not a bridge?

   In any xxx – yyy path using eee , replace eee by the rest of CCC (a uuu – vvv path avoiding eee ). This gives an xxx – yyy walk in G−eG - eG−e , and every xxx – yyy walk contains an xxx – yyy path. So the component of eee stays connected.

8. A graph with no cycles is acyclic; an acyclic connected graph is a tree.

   Trees are usually denoted TTT .

9. Why is every edge of a tree a bridge?

   A tree has no cycles, and an edge is a bridge exactly when it lies on no cycle. So a tree could be defined as a connected graph in which every edge is a bridge. Seven villages and six roads: closing any one road separates some villages.

10. How many trees of order 6 are there (up to isomorphism)?

    6 From the star T1=K1,5T_1 = K_{1,5}T1​=K1,5​ to the path T6=P6T_6 = P_6T6​=P6​ , with 5 down to 2 end-vertices.

11. What is a double star?

    A tree with exactly two vertices that are not end-vertices. Those two vertices are necessarily adjacent: two stars with their centers joined by an edge.

12. What is a caterpillar, and what is its spine?

    A tree of order at least 3 in which removing all end-vertices leaves a path; that path is the spine. Every path and star of order at least 3, and every double star, is a caterpillar.

13. Which of these trees are caterpillars?

    T′T'T′ and T′′T''T′′ are; T′′′T'''T′′′ is not. Removing the end-vertices of T′′′T'''T′′′ leaves a vertex with three neighbors, K1,3K_{1,3}K1,3​ , which is not a path.

14. What is a rooted tree, and how is it usually drawn?

    A tree with one vertex chosen as its root rrr . It is drawn with rrr at the top and the other vertices below, in levels by their distance from rrr . The same tree, drawn with root rrr at the top: levels at distance 1, 2, 3.

15. An acyclic graph is also called a forest.

    Each component of a forest is a tree. A tree is a connected forest.

16. Theorem 4.2 A graph GGG is a tree if and only if … ?

    Every two vertices of GGG are connected by a unique path.

17. A graph GGG is a tree if and only if every two vertices of GGG are connected by a unique path.What is the key idea of the proof in each direction?

    Two distinct uuu – vvv paths would produce a cycle; a cycle through uuu and vvv gives two distinct uuu – vvv paths. Unique paths also give connectedness, so the graph is connected and acyclic.

18. Theorem 4.3 How many end-vertices (vertices of degree 1) must every nontrivial tree have?

    At least two. Nontrivial: order at least 2.

19. Every nontrivial tree has at least two end-vertices.How does the proof find two end-vertices?

    The two ends u,vu, vu,v of a longest path PPP are end-vertices. A neighbor of uuu off PPP would give a longer path; a second neighbor of uuu on PPP would give a cycle.

20. TTT is a tree of order k+1≥2k + 1 \ge 2k+1≥2 and vvv is an end-vertex of TTT . What is T−vT - vT−v , and why is that useful?

    A tree of order kkk , which makes induction on the order work for trees. Removing an end-vertex keeps the graph connected and creates no cycle.

21. Theorem 4.4 What is the size (number of edges) of every tree of order nnn ?

    n−1\boldsymbol{n - 1}n−1

22. Every tree of order nnn has size n−1n - 1n−1 .How does the proof go?

    Induction on nnn : remove an end-vertex vvv . T−vT - vT−v is a tree of order n−1n - 1n−1 , so it has n−2n - 2n−2 edges by induction, and TTT has exactly one more edge.

23. A tree TTT of order 13 has only vertices of degree 1, 2 and 5, and exactly three vertices of degree 2. How many end-vertices does TTT have?

    8 TTT has 12 edges. With xxx end-vertices and 10−x10 - x10−x vertices of degree 5: x+2⋅3+5(10−x)=2⋅12x + 2 \cdot 3 + 5(10 - x) = 2 \cdot 12x+2⋅3+5(10−x)=2⋅12 , so x=8x = 8x=8 .

24. Corollary 4.6 What is the size of a forest of order nnn with kkk components?

    n−k\boldsymbol{n - k}n−k If component GiG_iGi​ has order nin_ini​ , it is a tree with ni−1n_i - 1ni​−1 edges, so m=∑i=1k(ni−1)=n−km = \displaystyle\sum_{i=1}^{k} (n_i - 1) = n - km=i=1∑k​(ni​−1)=n−k .

25. Theorem 4.7 What is a lower bound on the size of a connected graph of order nnn ?

    n−1\boldsymbol{n - 1}n−1 edges Trees attain this bound.

26. How does a proof by minimum counterexample work?

    Assume the statement is false, take a smallest counterexample, and derive an even smaller counterexample, a contradiction.

27. The size of every connected graph of order nnn is at least n−1n - 1n−1 .How does the proof by minimum counterexample go?

    A smallest counterexample GGG (order nnn , size m≤n−2m \le n - 2m≤n−2 ) has an end-vertex vvv , and G−vG - vG−v is a smaller counterexample. End-vertex: otherwise every degree is at least 2, so 2m≥2n2m \ge 2n2m≥2n . And G−vG - vG−v is connected with order n−1n - 1n−1 and size m−1≤n−3m - 1 \le n - 3m−1≤n−3 .

28. Theorem 4.8 A graph GGG has order nnn and size mmm . Of the properties (1) GGG is connected, (2) GGG is acyclic, (3) m=n−1m = n - 1m=n−1 , how many make GGG a tree?

    Any two of them. (1) and (2) is the definition of a tree; (1) and (3), and (2) and (3), each also suffice.

29. GGG has order nnn and size mmm . If GGG satisfies two of: (1) connected, (2) acyclic, (3) m=n−1m = n - 1m=n−1 , then GGG is a tree.Why does a connected GGG with m=n−1m = n - 1m=n−1 have no cycle?

    Deleting an edge of a cycle would leave a connected graph with only n−2n - 2n−2 edges, but a connected graph of order nnn has at least n−1n - 1n−1 edges. An edge on a cycle is not a bridge, so its deletion keeps GGG connected.

30. GGG has order nnn and size mmm . If GGG satisfies two of: (1) connected, (2) acyclic, (3) m=n−1m = n - 1m=n−1 , then GGG is a tree.Why is an acyclic GGG with m=n−1m = n - 1m=n−1 connected?

    GGG is a forest, so m=n−km = n - km=n−k with kkk components; n−1=n−kn - 1 = n - kn−1=n−k gives k=1k = 1k=1 .

31. Theorem 4.9 TTT is a tree of order kkk . Which condition on a graph GGG guarantees that TTT is isomorphic to a subgraph of GGG ?

    δ(G)≥k−1\boldsymbol{\delta(G) \ge k - 1}δ(G)≥k−1 (the minimum degree) e.g. every tree of order kkk is a subgraph of KkK_kKk​ , which has δ(Kk)=k−1\delta(K_k) = k - 1δ(Kk​)=k−1 .

32. If TTT is a tree of order kkk and δ(G)≥k−1\delta(G) \ge k - 1δ(G)≥k−1 , then TTT is isomorphic to a subgraph of GGG .How does the induction step of the proof go?

    Remove an end-vertex vvv (with neighbor uuu ), embed T−vT - vT−v as F⊆GF \subseteq GF⊆G , then join the copy u′u'u′ of uuu to a vertex www outside FFF . www exists: FFF has only k−1k - 1k−1 vertices, so u′u'u′ has at most k−2k - 2k−2 neighbors in FFF , but deg⁡Gu′≥k−1\deg_G u' \ge k - 1degG​u′≥k−1 .

33. GGG is a connected graph with cycles. How can you delete edges to get a tree with the same vertex set as GGG ?

    Repeatedly delete an edge lying on a cycle, until no cycle is left. An edge on a cycle is not a bridge, so the graph stays connected each time.

34. GGG is a connected graph of order nnn . How can you add edges to get a tree with the same vertex set as GGG ?

    Start with the empty graph on V(G)V(G)V(G) and add edges of GGG one at a time, never producing a cycle, until there are n−1n - 1n−1 edges. An acyclic graph of order nnn with n−1n - 1n−1 edges is a tree.

35. What is a spanning tree of a connected graph GGG ?

    A spanning subgraph of GGG that is a tree, i.e. a tree T⊆GT \subseteq GT⊆G with V(T)=V(G)V(T) = V(G)V(T)=V(G) . Two spanning trees T1,T2T_1, T_2T1​,T2​ of GGG .

36. Theorem 4.10. Which graphs contain a spanning tree?

    Exactly the connected graphs. Every connected graph has one; a graph with a spanning tree is connected.

37. Villages are to be joined by roads, every road having a positive cost. Why is a cheapest road network connecting all villages always a tree?

    If it had a cycle, a road on the cycle would not be a bridge, so dropping it keeps the network connected and lowers the cost.

38. In a weighted graph GGG (edge eee has weight w(e)w(e)w(e) ), what is the weight w(H)w(H)w(H) of a subgraph HHH ?

    The sum of the weights of its edges: w(H)=∑e∈E(H)w(e)\displaystyle w(H) = \sum_{e \in E(H)} w(e)w(H)=e∈E(H)∑​w(e) The weight of an edge is also called its cost.

39. What is a minimum spanning tree of a connected weighted graph GGG ?

    A spanning tree of GGG whose weight is minimum among all spanning trees of GGG . Finding one is the Minimum Spanning Tree Problem, important in designing computer, communication and transportation networks.

40. Who first formulated the Minimum Spanning Tree Problem, when, and why?

    Otakar Borůvka, 1926, for the most economical layout of a power-line network. He also gave its first solution. (History researched by Graham and Hell, 1985.)

41. How does Kruskal's Algorithm build a spanning tree of a connected weighted graph GGG ?

    Repeatedly select a remaining edge of minimum weight that produces no cycle with the edges already selected, until a spanning tree is produced. The selected edges need not form a connected graph along the way. Joseph Kruskal, 1956.

42. Run Kruskal's Algorithm on this weighted graph. Which edges are selected, in order, and what is the weight of the tree?

    uv (1), xy (2), vw (3), ux (4)\boldsymbol{uv\,(1),\ xy\,(2),\ vw\,(3),\ ux\,(4)}uv(1), xy(2), vw(3), ux(4) , weight 10 uw (4)uw\,(4)uw(4) is skipped: it would close the cycle u,v,wu, v, wu,v,w .

43. Theorem 4.11. What does Kruskal's Algorithm produce in a connected weighted graph?

    A minimum spanning tree.

44. Kruskal's Algorithm selects edges e1,e2,…,en−1e_1, e_2, \dots, e_{n-1}e1​,e2​,…,en−1​ of a tree TTT , each time a minimum-weight edge producing no cycle with the earlier ones.Why is TTT a minimum spanning tree? Give the key idea of the proof.

    Exchange argument: take a minimum spanning tree HHH sharing the most edges with TTT ; swapping the first edge eie_iei​ of TTT not in HHH into HHH gives a minimum spanning tree sharing even more. H+eiH + e_iH+ei​ has a cycle with an edge e0∉Te_0 \notin Te0​∈/T ; let T0=H+ei−e0T_0 = H + e_i - e_0T0​=H+ei​−e0​ . Then w(e0)≤w(ei)w(e_0) \le w(e_i)w(e0​)≤w(ei​) since HHH is minimum, and w(ei)≤w(e0)w(e_i) \le w(e_0)w(ei​)≤w(e0​) since e0e_0e0​ could also have been added to e1,…,ei−1e_1, \dots, e_{i-1}…

45. How does Prim's Algorithm build a spanning tree of a connected weighted graph GGG ?

    Start at any vertex uuu with a minimum-weight edge at uuu ; then repeatedly select a minimum-weight edge with exactly one end on the edges already selected. So the selected edges always form a tree that grows from uuu .

46. Who first discovered the algorithm known as Prim's Algorithm?

    Vojtěch Jarník, in 1930. Robert Prim published it in 1957.

47. Run Prim's Algorithm on this weighted graph, starting at uuu . Which edges are selected, in order?

    uv (1), vw (3), ux (4), xy (2)\boldsymbol{uv\,(1),\ vw\,(3),\ ux\,(4),\ xy\,(2)}uv(1), vw(3), ux(4), xy(2) , weight 10 The same tree as Kruskal's Algorithm gives here, but Kruskal's would take xy (2)xy\,(2)xy(2) second.

48. What is the main difference between the edges selected so far by Kruskal's and by Prim's Algorithm?

    Prim's always form a tree containing the start vertex; Kruskal's only form a forest (no cycles, possibly disconnected). Kruskal's takes the cheapest edge anywhere that creates no cycle; Prim's the cheapest edge leaving the current tree.

49. Theorem 4.12. What does Prim's Algorithm produce in a connected weighted graph?

    A minimum spanning tree.

50. Prim's Algorithm selects edges e1,…,en−1e_1, \dots, e_{n-1}e1​,…,en−1​ of a tree TTT ; each ek+1e_{k+1}ek+1​ is a minimum-weight edge joining the vertex set UUU of e1,…,eke_1, \dots, e_ke1​,…,ek​ to a vertex outside UUU .Why is TTT a minimum spanning tree? Give the key idea of the proof.

    Exchange argument: among minimum spanning trees sharing the most edges with TTT , take HHH containing e1,…,eke_1, \dots, e_ke1​,…,ek​ with kkk largest; swapping ek+1e_{k+1}ek+1​ into HHH gives a minimum spanning tree that contradicts this choice. The cycle of H+ek+1H + e_{k+1}H+ek+1​ has another edge e0e_0e0​ from UUU to outside UUU ; let T′=H+ek+1−e0T' = H + e_{k+1} - e_0T′=H+ek+1​−e0​ . Prim's choice gives w(ek+1)≤w(e0)w(e_{k+1}) \le w(e_0)w(ek+1​)≤w(e0​) , so T′T'T′ is also minimum…

51. When are two spanning trees of a labeled graph counted as different?

    When their edge sets are different. So a tree has exactly one spanning tree (itself), a connected graph that is not a tree has more than one, and a disconnected graph has none.

52. When counting spanning trees by hand, which fact about cycles splits the count into cases?

    Every spanning tree misses at least one edge of each cycle.

53. How many spanning trees does this graph have?

    15 Without e4e_4e4​ : drop one of the six outer edges, 6 trees. With e4e_4e4​ : drop one of e1,e3,e6e_1, e_3, e_6e1​,e3​,e6​ and one of e2,e5,e7e_2, e_5, e_7e2​,e5​,e7​ , 3⋅3=93 \cdot 3 = 93⋅3=9 trees.

54. How many spanning trees does this graph have?

    54, split by how many of e3,e5,e6e_3, e_5, e_6e3​,e5​,e6​ the tree contains. None: drop one of the other six edges, 6. Exactly one, e.g. e3e_3e3​ : drop one of e1,e2e_1, e_2e1​,e2​ and one of e4,e7,e8,e9e_4, e_7, e_8, e_9e4​,e7​,e8​,e9​ , so 3⋅2⋅4=243 \cdot 2 \cdot 4 = 243⋅2⋅4=24 . Exactly two, e.g. e3,e5e_3, e_5e3​,e5​ : drop one edge from each of the pairs {e1,e2},{e4,e8},{e7,e9}\{e_1, e_2\}, \{e_4, e_8\}, \{e_7, e_9\}{e1​,e2​},{e4​,e8​},{e7​,e9​} , so 3⋅23=243 \cdot 2^3 = 243⋅23=24 .

55. How many spanning trees do K3K_3K3​ and K4K_4K4​ have?

    K3K_3K3​ : 3, K4\ K_4 K4​ : 16 K4K_4K4​ : split by how many of v1v2,v1v3,v2v3v_1v_2, v_1v_3, v_2v_3v1​v2​,v1​v3​,v2​v3​ the tree contains (none, one, two): 1+6+9=161 + 6 + 9 = 161+6+9=16 .

56. Cayley Tree Formula (Theorem 4.15) How many distinct trees are there with a specified vertex set of nnn vertices?

    nn−2\boldsymbol{n^{n-2}}nn−2 Equivalently, the number of spanning trees of KnK_nKn​ . Arthur Cayley, 1889. In 1967 John W. Moon described ten different proofs.

57. Arthur Cayley worked in which profession for 14 years, and how much mathematics did he write during that time?

    As a lawyer, writing more than 200 mathematical papers. He published over 900 papers in his life, a number exceeded only by Euler, Erdős and Cauchy.

58. What is the (i,j)(i,j)(i,j) -cofactor of an n×nn \times nn×n matrix M=[mij]M = [m_{ij}]M=[mij​] ?

    (−1)i+jdet⁡(Mij)\boldsymbol{(-1)^{i+j} \det(M_{ij})}(−1)i+jdet(Mij​) , where MijM_{ij}Mij​ is MMM with row iii and column jjj deleted.

59. Matrix Tree Theorem (Theorem 4.16) GGG has vertices v1,…,vnv_1, \dots, v_nv1​,…,vn​ and adjacency matrix A=[aij]A = [a_{ij}]A=[aij​] . The number of spanning trees of GGG equals any cofactor of which n×nn \times nn×n matrix CCC ?

    cij={deg⁡viif i=j−aijif i≠j\boldsymbol{c_{ij} = \begin{cases} \deg v_i & \text{if } i = j \\ -a_{ij} & \text{if } i \ne j \end{cases}}cij​={degvi​−aij​​if i=jif i=j​ , i.e. degrees on the diagonal, −A-A−A elsewhere. Implicit in the work of Gustav Kirchhoff (1847), known for his laws of electrical currents.

60. GGG is the triangle v1v2v3v_1v_2v_3v1​v2​v3​ with an extra edge v3v4v_3v_4v3​v4​ . Count its spanning trees with the Matrix Tree Theorem (degrees on the diagonal of CCC , −1-1−1 for each edge off it).

    3, the (3,3)(3,3)(3,3) -cofactor of CCC . ∣2−10−120001∣=1⋅(4−1)=3\begin{vmatrix} 2 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 1 \end{vmatrix} = 1 \cdot (4 - 1) = 3∣∣​2−10​−120​001​∣∣​=1⋅(4−1)=3 , one spanning tree per edge of the triangle left out.