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) $3\times 3$ adjacency matrix $A$ for vertices $a,b,c$ (in that order), with a loop at $a$ ($A_{aa}=1$). (b) Complete bipartite graph $K_{m,n}$.

Find. (a) The number of length-3 walks $b\to c$ and $a\to c$. (b) The full characterization of $(m,n)$ pairs admitting an Euler path (open or closed).

Approach. (a) use the standard theorem that $(A^k)_{ij}$ counts walks of length $k$ from $i$ to $j$; compute $A^3$. (b) compute the degree of each vertex in $K_{m,n}$ and apply the Euler-path/-circuit degree theorems.

1. (a) Walks of length 3. Order vertices $(a,b,c)$ so $$A=\begin{pmatrix}1&1&0\\1&0&1\\0&1&0\end{pmatrix}$$ By the standard theorem, the $(i,j)$ entry of $A^k$ counts walks of length $k$ from $i$ to $j$. Computing $A^2=A\cdot A$ then $A^3=A^2\cdot A$: $$A^2=\begin{pmatrix}2&1&1\\1&2&0\\1&0&1\end{pmatrix},\qquad A^3=\begin{pmatrix}3&3&1\\3&1&2\\1&2&0\end{pmatrix}$$ Reading off $(b,c)$ (row 2, col 3) and $(a,c)$ (row 1, col 3): $$\boxed{\text{walks}_3(b,c)=2},\qquad\boxed{\text{walks}_3(a,c)=1}$$
2. (b) Euler path in $K_{m,n}$. In $K_{m,n}$, every vertex on the $m$-side has degree $n$ and every vertex on the $n$-side has degree $m$. An Euler path exists iff the graph is connected (always true here, for $m,n\ge1$) and the number of ODD-degree vertices is 0 (giving a closed Euler circuit) or exactly 2 (giving an open Euler path).
   • If $n$ is odd, all $m$ vertices on the $m$-side have odd degree; if $m$ is odd, all $n$ vertices on the $n$-side have odd degree.
   • Both $m,n$ even: zero odd-degree vertices → Euler circuit (a special case of an Euler path).
   • One of $m,n$ equals 2 and the other is odd: say $m=2$, $n$ odd. The $n$ vertices on the $n$-side have degree $m=2$ (even); the 2 vertices on the $m$-side have degree $n$ (odd). Exactly 2 odd-degree vertices → open Euler path (not a circuit).
   • Both $m,n$ odd and $\gt 1$: every vertex on both sides is odd-degree, giving $m+n\gt 2$ odd vertices: no Euler path.
   • Trivial case $m=n=1$: $K_{1,1}$ is a single edge, itself trivially an Euler path between its two (odd-degree-1) endpoints. A brute-force check over $m,n\le 7$ confirms exactly these families satisfy the odd-degree-count test. $$\boxed{K_{m,n}\text{ has an Euler circuit iff } m,n\text{ both even; an open Euler path iff } \{m,n\}=\{1,1\}\text{ or one of }m,n\text{ equals }2\text{ (the other odd)}}$$