Question 10 of 12

Question 10

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. The general Euler-circuit/path existence criteria (degree-parity theorem), and the degree structure of $K_n$ (every vertex degree $n-1$) and $K_{m,n}$ (the $m$-side vertices have degree $n$, the $n$-side vertices have degree $m$).

Find. Definitions of Euler circuit/path plus the existence conditions, specialized to $K_n$ and $K_{m,n}$.

Approach. State the general even-degree / at-most-two-odd-vertices theorem, then substitute each family's known degree sequence to translate the general condition into a condition purely on $n$ (for $K_n$) or on $m,n$ (for $K_{m,n}$).

1. 10a) Euler circuit — definition and condition. An Euler circuit is a closed walk that traverses every edge of a connected graph exactly once and returns to its starting vertex. A connected simple graph has an Euler circuit iff every vertex has even degree.
2. 10b) Euler path — definition and condition. An Euler path (or trail) traverses every edge exactly once but need not return to the start. A connected simple graph has an Euler path (that is not already a circuit) iff it has exactly two vertices of odd degree (the path must start at one and end at the other); more generally, an Euler path exists (circuit included as a special case) iff the number of odd-degree vertices is 0 or 2.
3. 10c) $K_n$ — Euler circuit. Every vertex of $K_n$ has degree $n-1$. This is even exactly when $n-1$ is even, i.e. when $n$ is odd. $\boxed{K_n \text{ has an Euler circuit} \iff n \text{ is odd} (n\geq3)}$ — e.g. $K_3,K_5,K_7,\dots$
4. 10d) $K_{m,n}$ — Euler circuit. The $m$ vertices on one side have degree $n$; the $n$ vertices on the other side have degree $m$. All degrees are even exactly when both $m$ and $n$ are even (and the graph is connected, true whenever $m,n\geq1$). $\boxed{K_{m,n} \text{ has an Euler circuit} \iff m \text{ and } n \text{ are both even}}$
5. 10e) $K_{m,n}$ — Euler path. Count odd-degree vertices in each parity case: if $m,n$ both even, all degrees are even (0 odd vertices — this is the circuit case, already an Euler path). If exactly one of $m,n$ is odd — say $n$ odd, $m$ even — the $m$-side vertices (degree $n$, odd) are all odd-degree, contributing $m$ odd vertices; for this to equal 2, need $m=2$. Symmetrically, $m$ odd & $n$ even needs $n=2$. If both $m,n$ are odd, every vertex on both sides is odd-degree, contributing $m+n$ odd vertices; for this to equal 2, need $m=n=1$ (the single-edge graph $K_{1,1}$). Combining all cases: $$\boxed{K_{m,n} \text{ has an Euler path} \iff (m,n \text{ both even}) \text{ or } (\{m,n\}=\{2,\,\text{odd}\}) \text{ or } (m=n=1)}$$