Question 12 of 12

Question 12 (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A proposed 25-vertex graph with every vertex of degree 5. (b) The complete graph family $K_n$. (c) $A^3$ for a 3-vertex graph $G$ with vertex order $a,b,c$. (d) The complete bipartite family $K_{m,n}$.

Find. (a) Whether such a graph can exist. (b) All $n$ for which $K_n$ is planar. (c) The $(b,c)$ entry's meaning and value. (d) All $(m,n)$ for which $K_{m,n}$ has an Euler path.

Approach. (a) apply the handshaking lemma (sum of degrees is always even); (b) recall Kuratowski's theorem / the classical planarity of $K_1$–$K_4$ and non-planarity of $K_5$; (c) use the standard adjacency-matrix-power theorem for walk counts; (d) classify Euler-path existence by the number of odd-degree vertices in $K_{m,n}$'s two degree classes.

1. (a) Can a graph have 25 vertices all of degree 5? The handshaking lemma states that the sum of all vertex degrees in any graph equals twice the number of edges, and is therefore always EVEN. Here the proposed sum is: $$\sum\deg(v) = 25\times5 = 125\ \ (\text{odd})$$ An odd degree sum is impossible for any graph, since $2|E|$ is always even: $\boxed{\text{NOT possible}\text{ — }125\text{ is odd, violating the handshaking lemma}}$
2. (b) For what $n$ is $K_n$ planar? $K_1,K_2,K_3,K_4$ can each be drawn in the plane with no crossing edges (direct construction: $K_4$ draws as a triangle with one vertex placed inside connected to all three corners). $K_5$ is the smallest complete graph that is NOT planar — this is the classical result underlying Kuratowski's theorem (a graph is non-planar iff it contains a subdivision of $K_5$ or $K_{3,3}$; $K_5$ trivially contains itself). Since $K_n$ for $n\ge5$ contains $K_5$ as a subgraph, none of them are planar either: $\boxed{K_n\text{ is planar exactly for }n\in\{1,2,3,4\}}$
3. (c) Paths of length 3 between $b$ and $c$ from $A^3$. A standard theorem of graph theory states that for the adjacency matrix $A$ of a graph with vertex order $v_1,\ldots,v_k$, the $(i,j)$ entry of $A^m$ equals the number of walks of length exactly $m$ from $v_i$ to $v_j$. With vertex order $a,b,c$ (rows/columns 1,2,3), the entry for $b\to c$ is row 2, column 3 of $A^3$: $$A^3 = \begin{bmatrix}4&5&2\\5&6&\mathbf{3}\\2&3&1\end{bmatrix} \quad\Rightarrow\quad (A^3)_{b,c} = 3$$ $\boxed{3\text{ paths (walks) of length 3 between }b\text{ and }c}$
4. (d) Euler path condition for $K_{m,n}$. In $K_{m,n}$, every vertex on the $m$-side has degree $n$ (connected to all $n$ vertices on the other side), and every vertex on the $n$-side has degree $m$. A connected graph has an Euler path iff it has exactly 0 odd-degree vertices (Euler circuit, a special closed case of Euler path) or exactly 2 odd-degree vertices. Count odd-degree vertices by cases: if $n$ is odd, all $m$ vertices on the $m$-side are odd-degree; if $m$ is odd, all $n$ vertices on the $n$-side are odd-degree. Case both even: 0 odd vertices — Euler circuit exists. Case $m$ odd, $n$ even: odd-degree count $=n$ (the $n$-side vertices, each of odd degree $m$); need this to equal 2, so $n=2$. Case $n$ odd, $m$ even: symmetric, need $m=2$. Case both odd: ALL $m+n$ vertices are odd-degree; need $m+n=2$, forcing $m=n=1$ (the single-edge graph $K_{1,1}$). Combining all cases and confirming against a brute-force check over small $(m,n)$: $$\boxed{K_{m,n}\text{ has an Euler path iff: }m,n\text{ both even; OR }m=2\text{ with }n\text{ odd; OR }n=2\text{ with }m\text{ odd; OR }m=n=1}$$