Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / R / 1

False. A connected graph has an Eulerian cycle exactly when every vertex has even degree. In $K_n$ every degree is $n-1$, so it has an Eulerian cycle precisely when $n$ is odd. The complete graph $K_4$ is a counterexample to the statement for all $n\ge 3$.

True. Label the vertices $1,\dots ,n$. The cycle $1,2,\dots ,n,1$ uses existing edges of the complete graph and visits every vertex once before returning. It is a Hamiltonian cycle for every $n\ge 3$.

True. Draw two nested squares and join corresponding corners. This is the hypercube graph: each square gives one four-cycle and the four connecting edges give the remaining coordinate direction. The edges have no crossings, furnishing a plane graph.

False. The cube has eight vertices and twelve edges. Euler formula for a connected planar graph for its connected plane graph gives $8-12+F=2$, soThe nested-square embedding has four faces between the squares, one inside the smaller square and the unbounded exterior face.

True. Represent a vertex of $Q_4$ by a four-bit string, with an edge changing exactly one bit. Color according to the parity of the sum of the bits. Every edge joins opposite parities, giving a proper two-coloring. Since the graph has edges, one color is impossible, so $\chi (Q_4)=2$.

False. In $K_{r,s}$ the $r$ vertices in one class have degree $s$, while the $s$ vertices in the other have degree $r$. For positive $r,s$, connectedness is automatic, and Euler's criterion requires both $r$ and $s$ to be even. Evenness of their sum alone allows both to be odd. For example $K_{1,3}$ has $r+s=4$ but all four degrees are odd, so it has no Eulerian cycle.

False. The four-cycle $C_4=K_{2,2}$ is bipartite, with alternating color classes, but contains a cycle and therefore is not a tree.

True. Choose a root of the tree and color every vertex according to the parity of its graph distance from that root. The unique-path property implies that the endpoints of each edge have distances differing by one. Thus every edge crosses the two color classes, proving bipartite graph.

False. In a Prüfer code, the degree of a label is one plus its number of occurrences. Here labels $1,\dots ,n-2$ occur once and labels $n-1,n$ do not occur. Thus the former have degree two and the latter degree one. The decoded tree is the pathwith the evident single-edge interpretation when $n=2$. Independently, no vertex of a simple tree on $n$ vertices can have degree $n$ at all. The degree claim in the statement is therefore impossible.

True. Each connected component of a forest is a tree. If the component sizes are $n_1,\dots ,n_k$, their edge counts are $n_1-1,\dots ,n_k-1$, including isolated vertices as size-one components. Summing gives $m=n-k$, hence