1. **Problem:** Prove that if $G$ is a tree graph, then the number of vertices $|V(G)|$ equals the number of edges $|E(G)|$ plus 1. 2. **Formula and rules:** A tree is a connected graph with no cycles. A fundamental property of trees is: $$|V(G)| = |E(G)| + 1$$ 3. **Proof:** - Start with a single vertex: $|V|=1$, $|E|=0$, so $1=0+1$ holds. - Adding one edge connects a new vertex, increasing $|V|$ by 1 and $|E|$ by 1. - By induction, after adding $k$ edges, $|V|=k+1$ and $|E|=k$. - Hence, $|V(G)| = |E(G)| + 1$ for any tree. --- 1. **Problem:** Using Prim's algorithm, find the minimal cable length to connect houses A, B, C, D, E, F with given edge weights. 2. **Prim's Algorithm:** Start from any vertex, repeatedly add the smallest edge connecting a new vertex until all vertices are connected. 3. **Step-by-step:** - Start at A. - Edges from A: AB=10, AC=7, AE=7, AF=12. Choose AC=7 (smallest). - Vertices connected: A, C. - Edges from A or C to new vertices: AB=10, AE=7, AF=12, BC=8, CD=6. - Choose AE=7 (smallest). - Vertices connected: A, C, E. - Edges from connected vertices: AB=10, AF=12, BC=8, CD=6, BE=5, DE=4, FE=2. - Choose FE=2 (smallest). - Vertices connected: A, C, E, F. - Edges from connected vertices: AB=10, BC=8, CD=6, BD=3, DE=4, DF=5. - Choose BD=3 (smallest). - Vertices connected: A, B, C, D, E, F. - All vertices connected. 4. **Sum of edges:** $7 + 7 + 2 + 3 + 6 = 25$ --- 1. **Problem:** Given a triangular arrangement of billiard balls, (a) express the graph, (b) find the minimal number of colors to color the balls so that no adjacent balls share the same color. 2. **Graph description:** Vertices arranged in rows: - Row 1: A, B, C, D, E - Row 2: F, G, H, I - Row 3: J, K, L - Row 4: M, N - Row 5: O Edges connect adjacent balls in the triangular lattice. 3. **Minimal coloring:** The graph is a planar triangular lattice, which is 3-colorable. 4. **Answer:** Minimum colors needed = 3. --- **Final answers:** - For problem 1: $|V(G)| = |E(G)| + 1$ - For problem 2: Minimal cable length = 25 - For problem 3: Minimal colors = 3