Question 12 of 12

Question 12

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. Four short graph-theory questions.

Find. (a) existence of a 13-vertex, all-degree-7 graph. (b) number of length-5 walks between $b$ and $c$ from $A^5$. (c) maximum left-side degree in the described bipartite graph. (d) values of $n$ for which $K_n$ is planar.

Approach. (a) apply the handshake lemma (sum of degrees is always even). (b) read the $(b,c)$ entry of $A^5$ directly — that IS the count of length-5 walks between $b$ and $c$. (c) use the fact that the two sides of a bipartite graph have equal degree sums, plus the minimum-degree-1 requirement for connectivity. (d) compare $K_n$'s edge count against the maximum edge count a simple planar graph on $n$ vertices can have.

1. a) 13 vertices, all degree 7 — possible? By the handshake lemma, $\sum_v\deg(v)=2|E|$ is always even. Here $\sum\deg(v)=13\times7=91$, which is odd. $\boxed{\text{No}}$ — a graph with 13 vertices all of degree 7 cannot exist, since its degree sum would be odd, contradicting the handshake lemma.
2. b) Paths of length 5 between $b$ and $c$. For an adjacency matrix $A$, the $(i,j)$ entry of $A^k$ counts the walks of length exactly $k$ from vertex $i$ to vertex $j$ (proved by induction on $k$: $(A^{k})_{ij}=\sum_m(A^{k-1})_{im}A_{mj}$ extends every length-$(k-1)$ walk by one edge). With rows/columns ordered $a,b,c$, the $(b,c)$ entry is row 2, column 3: $\boxed{7}$. The printed matrix is symmetric ($(A^5)_{cb}=7$ as well), as it must be for an undirected graph, so the count is the same in either direction. ("Paths" here means walks, the standard reading for adjacency-matrix powers; vertices and edges may repeat.)
3. c) Maximum possible degree on the left side. The right side has 5 vertices each of degree 2, so the total edge count is $5\times2=10$; since every edge in a bipartite graph has exactly one endpoint on each side, the left side's degrees also sum to 10. For the graph to be connected, every one of the 7 left vertices must have degree $\ge1$ (an isolated vertex would disconnect the graph). To maximize one left vertex's degree, give the other 6 left vertices the minimum degree 1 each (using $6\times1=6$ of the budget), leaving $10-6=\boxed{4}$ for the remaining vertex. (The simple-graph cap of 5, one edge to each right vertex, does not bind.)

4. d) For what $n$ is $K_n$ planar? $K_n$ has $\binom{n}{2}=n(n-1)/2$ edges. A simple planar graph on $v\ge3$ vertices can have at most $3v-6$ edges. Check each small case directly: $K_1,K_2,K_3,K_4$ are all planar by direct construction ($K_4$ draws with one crossing-free layout — a triangle with a center vertex joined to all three corners). For $K_5$: edges $=\binom52=10$, but the planar bound is $3(5)-6=9<10$, so $K_5$ exceeds the maximum possible edge count for a simple planar graph — $K_5$ is NOT planar (this is also the classical Kuratowski-subgraph obstruction). For $n\ge5$, $K_n$ contains $K_5$ as a subgraph, so no $K_n$ with $n\ge5$ is planar either. $\boxed{K_n\text{ is planar exactly for } n\in\{1,2,3,4\}}$.