Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A (Graph Theory)

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because the distinct matched partners of $S$ belong to $N(S)$.

For sufficiency take a maximum matching. If it leaves $x\in L$ unmatched, explore alternating paths starting at $x$, traversing unmatched edges from left to right and matched edges back to the left. No reached right vertex can be unmatched, since flipping the edges of such an alternating path would augment the matching. Let $S,T$ be the reached left and right sets. Every neighbour of $S$ lies in $T$: unmatched edges are explored, and a matched edge from a reached left vertex leads to its already reached predecessor. Conversely every member of $T$ is a neighbour of $S$. Their matched partners are exactly $S\setminus \{x\}$, so $|N(S)|=|T|=|S|-1$, contradicting the hypothesis. Thus a matching covering $L$ exists.

If no complete matching exists, Hall's theorem gives a nonempty $S\subseteq V_1$, of size $k$, with $|N(S)|\le k-1$. The pairs between $S$ and $V_2\setminus N(S)$ must be nonedges, so there are at leastmissing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore a complete matching exists.

The strictness is necessary: isolate one vertex of $V_1$ and put all edges between the remaining $n-1$ left vertices and all $n$ right vertices. There are exactly $n(n-1)$ edges and no matching can cover the isolated vertex. This also handles $n=1$.

First the graph is connected: every component has at least $\delta (G)+1>n/2$ vertices, so two components cannot fit. Take a longest path $v_1,\dots ,v_k$. Every neighbour of either endpoint lies on that path. In the index set $\{1,\dots ,k-1\}$ defineTheir sizes sum to $d(v_1)+d(v_k)\ge n>k-1$, so they share an index $i$. The edges at that index give the cyclecontaining every vertex of the path. The minimum-degree assumption and $n\ge 3$ ensure the resulting cycle is nondegenerate. If it omitted any graph vertex, connectedness would supply an edge from outside it to the cycle. Starting with that outside vertex and then following the cycle without closing it gives a path with $k+1$ vertices, contradicting maximality. Thus the cycle is Hamiltonian. This proves Dirac's theorem in the required case.

For a positive integer $x$, the chromatic polynomial $p_G(x)$ counts proper vertex colorings from a palette of $x$ labelled colors, where adjacent vertices must have different colors. The counting function agrees with a polynomial, as proved by deletion-contraction in the next part.

For an edge $e=uv$, colorings of $G-e$ divide into those giving $u,v$ different colors, counted by $p_G$, and those giving them the same color, counted by $p_{G/e}$. Parallel edges produced by contraction may be suppressed. ThusFor an edgeless graph on $n\ge 1$ vertices, $p_G=x^n$. Induct on the number of edges, allowing smaller vertex counts for contractions. If both smaller expansions have alternating nonnegative coefficients, the contraction's leading degree is one lower, so subtracting it giveswith absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion isThis induction simultaneously proves the counting function is a polynomial.

For a triangle, $p_{C_3}=x(x-1)(x-2)=(x-1{)}^3-(x-1)$. For $n\ge 4$, deleting an edge leaves a path with polynomial $x(x-1{)}^{n-1}$, and contracting it leaves $C_{n-1}$. Deletion-contraction and induction giveThe path formula chooses its first color freely and each succeeding color in $x-1$ ways.

Choose the central vertex's color in $x$ ways. Every rim vertex must avoid that color, so the rim is a cycle colored using the remaining $x-1$ colors. Hence

The Ramsey number $R(k,l)$ is the least $N$ such that every graph on $N$ vertices has a $k$-clique or an independent set of size $l$. Choose a vertex in a graph of order $R(k-1,l)+R(k,l-1)$. It has either at least $R(k-1,l)$ neighbours or at least $R(k,l-1)$ nonneighbours. In the first set, a $(k-1)$-clique extends with the vertex to a $k$-clique, while an independent $l$-set already suffices. The complementary argument handles the second set. ThusThe boundary values are $R(k,2)=k$ and $R(2,l)=l$. Induction on $k+l$, using Pascal's identity, therefore gives

The graph Ramsey number $R(G,H)$ is the smallest $N$ such that every red-blue coloring of the edges of $K_N$ has a red copy of $G$ or a blue copy of $H$. These copies are subgraphs, not necessarily induced. Equivalently every graph on $N$ vertices contains $G$ or its complement contains $H$.

For $s,t\ge 2$, split $(s-1)(t-1)$ vertices into $s-1$ classes of size $t-1$, coloring edges between classes red and edges inside classes blue. The red graph has no $K_s$, and every blue component is too small for the connected tree. This proves the lower bound.

For the upper bound let $N=(s-1)(t-1)+1$ and suppose the blue graph contains no copy of the tree. By the permitted chromatic-number statement, its chromatic number is at most $t-1$. A graph of larger chromatic number would have a subgraph of chromatic number exactly $t$, obtained by deleting vertices until that number is reached. A proper blue coloring with at most $t-1$ classes puts no blue edges within any class, so each class is a red clique. If there is no red $K_s$, each class has at most $s-1$ vertices, contradicting $N>(s-1)(t-1)$. ThereforeThe one-vertex boundary cases give one directly.

A vertex with at least $R(t,t)$ neighbours has either a $t$-clique among them, producing $K_{t+1}$ with the vertex, or an independent $t$-set among them, producing an induced star with that centre.

For the second assertion put $D=R(t,t)-1$. If either of those two outcomes is absent, the preceding result forces maximum degree at most $D$. In a connected graph of this maximum degree, a ball of radius $t-1$ has at most $1+D+\cdots +D^{t-1}$ vertices, using the rough bound on walks at each distance. If the graph has more vertices, some vertex lies at distance at least $t$ from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first $t$ edges give an induced path of the required length. Thus a sufficiently large connected graph has one of the three listed configurations.

The extremal number $\mathrm{ex}(n;H)$ is the maximum number of edges in a simple graph on $n$ vertices containing no subgraph isomorphic to $H$. For a fixed graph with $\chi (H)=r\ge 2$, the Erdős-Stone theorem givesEquivalently, the ratio to $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ tends to $1-1/(r-1)$. The bipartite case has limiting density zero.

An even cycle is bipartite and has chromatic number two. An odd cycle has chromatic number three. The extremal-density theorem therefore givesFor odd cycles the complete balanced bipartite graph also exhibits the matching asymptotic lower density one half.

For nonempty disjoint vertex sets define $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is $ϵ$-uniform, also called regular, if whenever $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ have sizes at least $ϵ|X|$ and $ϵ|Y|$,Thus reasonably large relative subsets retain almost the same edge density.

Let $S$ be the vertices of $X$ with fewer than $d|Y|/2$ neighbours in $Y$. If $|S|>ϵn$, it is a permissible subset in the regularity test, and averaging those degrees gives $d(S,Y)<d/2$. But $d(X,Y)\ge d$, socontradicting regularity. Therefore there are at most $ϵn$ such vertices. The same argument in fact rules out $|S|\ge ϵn$ when that threshold is integral and nonzero.

Retain $0<ϵ<d/2$ from the preceding part. In $X_1$, at most $ϵn$ vertices have too few neighbours in $X_2$, and at most $ϵn$ have too few in $X_3$. Since $d\le 1$, $2ϵ<1$, so some $x\in X_1$ is good for both. Put $Y_2=N(x)\cap X_2$ and $Y_3=N(x)\cap X_3$. Their sizes are at least $dn/2>ϵn$. Regularity of $(X_2,X_3)$ therefore givesThere is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form a triangle. The nonempty equal classes ensure this counting argument also covers small integer sizes.