Question 11 of 12

Question 11

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 1-skeleton (vertex-edge graph) of each named polyhedron, and the complete bipartite family $K_{m,n}$.

Find. (a) definition + existence condition for an Euler circuit. (b) the (m,n) values for which $K_{m,n}$ has one. (c) definition of a Hamilton path. (d) whether each of the three polyhedral graphs has a Hamilton path.

Approach. Use the classical theorem that a connected graph has an Euler circuit iff every vertex has even degree; compute the (regular) vertex degrees of $K_{m,n}$ directly from its bipartite structure; for Hamilton paths, exhibit an explicit visiting order on each small polyhedral graph.

1. Part (a) — Euler circuit, definition and condition. An Euler circuit is a closed walk that traverses every edge of the graph exactly once and returns to its starting vertex. $$\boxed{\text{A connected graph has an Euler circuit} \iff \text{every vertex has even degree}}$$ (Euler's theorem: the walk must enter and leave each visited vertex the same number of times except possibly matching at start/end, and since the circuit is closed even the start/end vertex needs even degree.)
2. Part (b) — K_m,n, Euler circuit condition. 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. $K_{m,n}$ is connected whenever $m,n\ge1$. By part (a), an Euler circuit exists iff every vertex has even degree, i.e. the m-side's common degree n is even and the n-side's common degree m is even: $$\boxed{K_{m,n} \text{ has an Euler circuit} \iff m \text{ and } n \text{ are both even}}$$.
3. Part (c) — Hamilton path, definition. A Hamilton path is a path that visits every vertex of the graph exactly once (edges need not be reused, and unlike an Euler circuit there is no requirement to use every edge or to return to the start).
4. Part (d) — Hamilton paths on tetrahedron, cube, octahedron. Tetrahedron (4 vertices, every pair adjacent — this is $K_4$): any ordering of all 4 vertices is automatically a valid path since every pair is connected, e.g. $1\to2\to3\to4$. Yes. Cube (8 vertices, 3-regular, vertices = 3-bit binary strings with edges between strings differing in one bit): an explicit Hamilton path is the standard binary-reflected Gray code sequence $000\to001\to011\to010\to110\to111\to101\to100$, where each consecutive pair differs in exactly one bit (hence is an edge). Yes. Octahedron (6 vertices, 4-regular, each vertex adjacent to every other vertex except its own antipode): e.g. label the three antipodal pairs $\{1,1'\},\{2,2'\},\{3,3'\}$; the path $1\to2\to1'\to3\to2'\to3'$ visits all 6 vertices, each step going between non-antipodal (hence adjacent) vertices. Yes. $$\boxed{\text{All three (tetrahedron, cube, octahedron) graphs have a Hamilton path}}$$