Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / R (Graph Theory)

Suppose a graph satisfying Ore's theorem were not Hamiltonian. Extend it, on the same vertices, to an edge-maximal non-Hamiltonian graph $H$. Adding edges preserves the degree-sum hypothesis. The complete graph is Hamiltonian, so $H$ has a missing edge $uv$. By maximality, $H+uv$ has a Hamiltonian cycle, which must use the new edge. Removing it gives a Hamiltonian path in $H$, labelled $u=v_1,v_2,\dots ,v_n=v$.

If some $i$ has both edges $u{v}_{i+1}$ and $v{v}_i$, the path can be closed into the cyclecontradicting the choice of $H$. Thus the index sets $\{i:u{v}_{i+1}\in E(H)\}$ and $\{i:v{v}_i\in E(H)\}$ are disjoint subsets of $\{1,\dots ,n-1\}$. Their sizes are ${\mathrm{deg}}_{H}u$ and ${\mathrm{deg}}_{H}v$. Consequently ${\mathrm{deg}}_{H}u+{\mathrm{deg}}_{H}v\le n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original graph is Hamiltonian.

Take a complete graph on vertices $a,b,c,d$ and add a fifth vertex $v$ joined only to $a$ and $b$. The minimum degree is two, which is less than $5/2$. The only nonadjacent pairs are $(v,c)$ and $(v,d)$, and each has degree sum $2+3=5$. Thus Ore's condition holds even though the minimum-degree condition fails. For example,is a Hamiltonian cycle in this graph.

Represent the two sides of the marriage problem as the parts $L,R$ of a bipartite graph, with an edge for each allowed pairing. A matching is a set of edges with no common endpoint; a complete matching of $L$ covers every vertex in $L$. When the two parts have equal size it also covers $R$, giving a perfect matching.

Hall's marriage theorem gives the exact finite-graph criterion:Here $N(S)$ is the set of right-side neighbours of $S$. Necessity follows because distinct matched vertices of $S$ need distinct neighbours; Hall's theorem supplies sufficiency.

Let $k=\chi (G)$. For $k\le 1$ the bound is immediate. Otherwise choose a vertex-minimal subgraph $H$ with chromatic number $k$. Each vertex has degree at least $k-1$ in $H$: if one had degree at most $k-2$, a $(k-1)$-colouring of the smaller graph obtained by deleting it could be extended to it using an absent neighbour colour, contradicting $\chi (H)=k$.

The graph $H$ has at least $k$ vertices. By the degree-sum identity,Solving the quadratic inequality gives

Root the tree at any vertex and order vertices so every parent precedes its children. The root has $k$ colour choices. Each of the other $n-1$ vertices has exactly one earlier adjacent vertex, its parent, and therefore exactly $k-1$ choices. There are no other restrictions because a tree has no cycles and no extra edges between those branches. Multiplication yieldsThe formula also includes the one-vertex tree.

In the complete graph every pair of vertices is adjacent, so all $n$ colours assigned to vertices must be distinct. Choose colours successively, leaving one fewer choice at each step. ThusFor nonnegative integer $k<n$ the product is zero, as required.