1. **Prove that Complete Graph K₄ is Planar** The problem is to prove that the complete graph on 4 vertices, $K_4$, can be drawn on a plane without any edges crossing. **Step 1:** Recall that a graph is planar if it can be drawn on a plane without edges crossing. **Step 2:** $K_4$ has 4 vertices and every vertex is connected to every other vertex, so it has $\binom{4}{2} = 6$ edges. **Step 3:** Draw the 4 vertices as points forming a triangle with one vertex inside. **Step 4:** Connect all vertices with edges. The edges can be drawn so that none cross by placing one vertex inside the triangle formed by the other three and connecting edges accordingly. **Step 5:** Since such a drawing exists, $K_4$ is planar. --- 2. **Define Isomorphism and Explain with Example** **Step 1:** Isomorphism between two graphs means there is a one-to-one correspondence between their vertex sets that preserves adjacency. **Step 2:** Formally, graphs $G$ and $H$ are isomorphic if there exists a bijection $f: V(G) \to V(H)$ such that any two vertices $u,v$ are adjacent in $G$ if and only if $f(u), f(v)$ are adjacent in $H$. **Step 3:** Example: Two graphs with vertices $\{a,b,c\}$ and $\{x,y,z\}$ where edges correspond under $f(a)=x$, $f(b)=y$, $f(c)=z$. **Step 4:** If edges $a-b$, $b-c$ exist in $G$, and edges $x-y$, $y-z$ exist in $H$, then $G$ and $H$ are isomorphic. --- 3. **Define Binary Trees and Traversals with Example** **Step 1:** A binary tree is a tree where each node has at most two children: left and right. **Step 2:** Traversals are methods to visit all nodes: - Inorder (Left, Root, Right) - Preorder (Root, Left, Right) - Postorder (Left, Right, Root) **Step 3:** Given tree: - Root: F - Left child of F: B - Left child of B: C - Right child of B: D - Right child of D: E - Right child of F: G - Right child of G: I - Left child of I: H **Step 4:** Inorder traversal: C, B, D, E, F, G, H, I **Step 5:** Preorder traversal: F, B, C, D, E, G, I, H **Step 6:** Postorder traversal: C, E, D, B, H, I, G, F --- 4. **Two Ways of Representing a Graph with Example** **Step 1:** Graphs can be represented by: - Adjacency Matrix - Adjacency List **Step 2:** Given tree: - Root: F - Left child: B - Right child: G - B's children: A (left), D (right) - A's children: C (left), E (right) - G's right child: I - I's left child: H **Step 3:** Adjacency Matrix is a square matrix where entry $(i,j)$ is 1 if vertices $i$ and $j$ are connected, else 0. **Step 4:** Adjacency List lists each vertex and its adjacent vertices. --- 5. **Define Euler's Formula and Prove for Given Graph** **Step 1:** Euler's formula for planar graphs: $$V - E + F = 2$$ where $V$=vertices, $E$=edges, $F$=faces. **Step 2:** Given graph has vertices $A,B,C,D,E$ ($V=5$). **Step 3:** Edges: $A-B$, $B-C$, $C-E$, $E-D$, $D-A$, $B-E$ ($E=6$). **Step 4:** Count faces $F$ including the outer face. **Step 5:** Faces are 3: triangle $B-C-E$, quadrilateral $A-B-E-D$, and outer face. **Step 6:** Check Euler's formula: $5 - 6 + 3 = 2$ which holds. --- 6. **Prove Unique Path Between Every Pair of Vertices in a Tree** **Step 1:** A tree is a connected acyclic graph. **Step 2:** Suppose two distinct paths exist between vertices $u$ and $v$. **Step 3:** Then combining these paths forms a cycle, contradicting acyclicity. **Step 4:** Hence, there is exactly one path between any two vertices. --- 7. **Define Spanning Tree and Explain Algorithm** **Step 1:** A spanning tree of a graph is a subgraph that is a tree including all vertices. **Step 2:** Algorithms to find spanning trees include: - Depth-First Search (DFS) - Breadth-First Search (BFS) - Kruskal's Algorithm - Prim's Algorithm **Step 3:** For example, Kruskal's algorithm sorts edges by weight and adds edges without forming cycles until all vertices are connected. --- 8. **Prove Two Graphs are Isomorphic** **Step 1:** Given two graphs with vertices $a,b,c,d,e,f$ and edges forming hexagon with diagonals. **Step 2:** Map vertices of Graph 1 to Graph 2 preserving adjacency. **Step 3:** Check edges correspond under mapping. **Step 4:** Since adjacency is preserved, graphs are isomorphic. --- 9. **Calculate Number of Edges in Complete Bipartite Graph $K_{3,4}$** **Step 1:** $K_{m,n}$ has $m$ vertices in one set and $n$ in the other. **Step 2:** Number of edges is $m \times n$. **Step 3:** For $K_{3,4}$, edges = $3 \times 4 = 12$. --- 10. **Define Hamiltonian Path and Cycle and Find for Given Graph** **Step 1:** Hamiltonian Path visits every vertex exactly once. **Step 2:** Hamiltonian Cycle is a Hamiltonian Path that starts and ends at the same vertex. **Step 3:** For given graph, find sequence of vertices covering all once. **Step 4:** Example path: 1-2-3-4-5-6-7 **Step 5:** If path returns to 1, it forms a cycle. --- 11. **Define Graph Coloring and Find Chromatic Number** **Step 1:** Graph coloring assigns colors to vertices so adjacent vertices have different colors. **Step 2:** Chromatic number is minimum colors needed. **Step 3:** For given graph, assign colors stepwise ensuring no two adjacent vertices share color. **Step 4:** Count minimum colors used. --- 12. **Find Number of Vertices of Degree 1 in Tree** **Step 1:** Sum of degrees in tree = $2 \times$ number of edges. **Step 2:** For tree with $n$ vertices, edges = $n-1$. **Step 3:** Given degrees: two vertices degree 2, one degree 3, three degree 4, and unknown number $x$ degree 1. **Step 4:** Sum degrees: $2\times2 + 1\times3 + 3\times4 + x\times1 = 2(n-1)$. **Step 5:** Let total vertices $n = 2 + 1 + 3 + x = 6 + x$. **Step 6:** Sum degrees: $4 + 3 + 12 + x = 19 + x$. **Step 7:** $19 + x = 2(6 + x - 1) = 2(5 + x) = 10 + 2x$. **Step 8:** Solve: $19 + x = 10 + 2x \Rightarrow 9 = x$. **Step 9:** Number of vertices degree 1 is 9. --- 13. **Find Number of Vertices in Graph G** **Step 1:** Sum of degrees = $2 \times$ edges = $2 \times 21 = 42$. **Step 2:** Given 3 vertices degree 4, others degree 3. **Step 3:** Let number of vertices be $n$, number of degree 3 vertices be $n-3$. **Step 4:** Sum degrees: $3 \times 4 + (n-3) \times 3 = 12 + 3n - 9 = 3n + 3$. **Step 5:** Set equal to 42: $3n + 3 = 42 \Rightarrow 3n = 39 \Rightarrow n = 13$. --- 14. **Find Six Spanning Trees of Given Graph** **Step 1:** Spanning trees are subgraphs connecting all vertices without cycles. **Step 2:** Enumerate different edge sets connecting all vertices with $V-1$ edges. **Step 3:** List six distinct spanning trees. --- 15. **Find Number of Edges in Graph with Given Degrees** **Step 1:** Sum degrees = $0 + 2 + 2 + 3 + 9 = 16$. **Step 2:** Number of edges = sum degrees / 2 = $16/2 = 8$. --- 16. **Rooted Tree: Find Root, Leaves, Internal Vertices** **Step 1:** Root is top node (given). **Step 2:** Leaves are nodes with no children. **Step 3:** Internal vertices have at least one child. --- 17. **Define Chromatic Number and Find for Given Graphs** **Step 1:** Chromatic number is minimum colors needed for proper coloring. **Step 2:** For bipartite graph $K_{3,4}$, chromatic number is 2. **Step 3:** For Hamiltonian graph, assign colors ensuring no adjacent vertices share color. **Step 4:** For colorful graph, count minimum colors used. **Step 5:** For tree, chromatic number is 2. **Step 6:** For linear and branching graph, find minimum colors similarly. --- **Final answers:** - $K_4$ is planar. - Isomorphism defined and example given. - Binary tree traversals explained. - Graph representations explained. - Euler's formula verified. - Unique path in tree proven. - Spanning tree defined with algorithm. - Graphs isomorphic. - Edges in $K_{3,4}$ = 12. - Hamiltonian path and cycle defined. - Chromatic number defined and found. - Number of degree 1 vertices = 9. - Number of vertices in $G$ = 13. - Number of edges with given degrees = 8. - Root, leaves, internal vertices identified.