Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / R / 2

For a finite graph choose a simple path of maximum length. Every neighbor of its final vertex must already lie on the path, since otherwise that vertex could be appended. The final vertex has degree at least two, so besides its predecessor it has another neighbor earlier on the path. That edge together with the intervening path segment makes a cycle in a graph.

Finiteness is needed for this assertion in general: the two-sided infinite path has degree two at every vertex and no cycle in a graph. The customary finite-graph convention is used here and in the subsequent cube questions.

For a closed Eulerian trail, every visit to a vertex pairs one entering edge with one departing edge, including the initial/final vertex. Thus every degree is even.

Conversely, in a finite connected graph with all degrees even, start at a vertex and follow unused edges until no extension is possible. The walk cannot stop away from its starting point: at a different endpoint an odd number of its incident edges would have been used, leaving at least one unused edge because its total degree is even. Thus it closes. If any edge remains unused, connectedness gives a vertex of the current closed trail incident with an unused edge. Repeat the construction from that vertex in the unused-edge subgraph and splice the resulting closed trail into the first one. Finitely many edges make the procedure terminate in a closed trail using every edge exactly once.

Hence a connected finite graph has an Eulerian circuit exactly when all degrees are even. If “trail” is allowed to be open, the printed equivalence needs correction: a connected graph has an Eulerian trail when it has zero or two odd-degree vertices. A single edge is an immediate counterexample to the unqualified printed statement.

Label vertices by triples of bits and join pairs differing in exactly one bit. Draw the four vertices with first bit zero as an outer square, and the four with first bit one as an inner square, in the same cyclic order $00,01,11,10$ for the last two bits. Connect corresponding corners by four nonintersecting spokes. Every cube edge is present and there are no crossings, giving the required planar embedding.

Opposite vertices differ in all three bits. Thus the four added edges areThey form a perfect matching and raise the degree of every vertex by one.

Every cube vertex has degree three, so $Q_3$ is not Eulerian; it even has eight odd-degree vertices, so has no open Eulerian trail. After the four diagonals are added every vertex has degree four, and the graph remains connected. Thus $Q_3^{\prime }$ is Eulerian, by the circuit criterion proved above.

Both are Hamiltonian. A Hamiltonian cycle already in the cube isSuccessive triples differ in exactly one bit, and each of the eight vertices occurs exactly once before returning. Adding edges preserves this cycle in a graph.

Both are bipartite. Partition the vertices by parity of the number of one bits. A cube edge changes one bit and an interior diagonal changes three bits, so both types join opposite parity classes. In fact $Q_3^{\prime }$ is $K_{4,4}$: from any vertex its three cube neighbors and its opposite vertex exhaust the four vertices of opposite parity.

Yes. Colour an even-parity vertex one colour and an odd-parity vertex the other. Every cube edge changes parity, so this is a proper two-colouring. At least two colours are needed because edges exist.

No. At any cube vertex its three incident faces are pairwise adjacent along the three incident edges. They would therefore require three different colours. Equivalently the dual of the planar cube embedding contains a triangle, which obstructs a face two-colouring.

As established above, $Q_3^{\prime }\cong K_{4,4}$. Select any three vertices in each parity class; all nine edges between the two triples are present, giving a $K_{3,3}$ subgraph. A planar graph has only planar subgraphs, whereas $K_{3,3}$ is nonplanar by the permitted result. Therefore $\boxed{Q_3^{\prime }\text{ is nonplanar}}$.