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

Hall's marriage theorem says that a finite bipartite graph with parts $L,R$ has a matching covering $L$ if and only if $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because matching edges send the vertices of $S$ to distinct neighbours.

For sufficiency, choose a maximum matching $M$. If it misses $a\in L$, explore all alternating paths from $a$, taking unmatched edges from left to right and matched edges from right to left. Let $S\subseteq L$ and $T\subseteq R$ be the reached vertices. No vertex of $T$ can be unmatched, since flipping the edges along the resulting augmenting path would enlarge $M$.

Every neighbour of a reached left vertex is reached on the right: unmatched edges are exploration steps, and a matched edge leads back to an already reached matching partner. Thus $T=N(S)$. Each right vertex in $T$ is matched to a reached left vertex other than $a$, and every reached left vertex other than $a$ arose this way. These matching partners give a bijection $T\leftrightarrow S\setminus \{a\}$. Hence $|N(S)|=|S|-1$, contradicting the assumed inequality. Therefore the maximum matching covers $L$.

Write the bipartition as $L,R$. Counting edges by their left and right ends gives $2009|L|=2009|R|$, so the parts have equal size. Put $H=G-F$. If some $S\subseteq L$ violated Hall's marriage theorem in $H$, let $T=N_H(S)$, so $|T|\le |S|-1$.

There are $2009|S|$ edges of $G$ incident with $S$, of which at most $2009|T|$ can end in $T$. Thus at least $2009(|S|-|T|)\ge 2009$ end in $R\setminus T$. All those edges must have been deleted, by the definition of $T$. This contradicts $|F|=2008$. Hence $H$ has a matching covering $L$, and equal part sizes make it a perfect matching avoiding every edge of $F$.

False. The path graph on four vertices is bipartite and its first and last edges form a perfect matching. It has no cycle at all, so it has no Hamiltonian cycle. This counterexample is connected as well.

True. Every cycle in a bipartite graph has even length because its vertices alternate between the two parts. On a Hamiltonian cycle, choose every other edge. These edges are disjoint and cover every vertex exactly once, so they form a perfect matching.

False. The complete bipartite graph $K_{2009,2010}$ is $2009$-connected. Deleting fewer than $2009$ vertices leaves at least one vertex in each part and therefore a connected complete bipartite graph; deleting the smaller part disconnects the larger independent set. But its two parts have unequal sizes, so a matching cannot cover them both. Equivalently it has an odd number of vertices. Thus it has no perfect matching.

For a finite simple loopless graph, $p_G(q)$ counts proper vertex colorings with $q$ labelled available colors, initially for nonnegative integer $q$. For an edge $e=uv$, proper colorings of $G-e$ split into those with different endpoint colors, counted by $p_G(q)$, and those with equal endpoint colors, counted by the contracted graph. Hence the deletion-contraction recurrence for the chromatic polynomial isParallel edges created by contraction can be suppressed since they impose the same coloring constraint. A graph with no edges has $p_G(q)=q^{|V(G)|}$. Induction by this recurrence therefore gives a polynomial agreeing with the counting function on all nonnegative integers. That polynomial is unique because two distinct polynomials cannot agree at infinitely many points.

Induct using the same deletion-contraction recurrence for the chromatic polynomial. The edgeless graph has polynomial $x^n$, so its leading coefficient is one and the others are zero. All nonempty-vertex chromatic polynomials have zero constant term, since no coloring uses zero colors.

For an existing edge, write the alternating coefficient lists of the deletion and simplified contraction as $a_i^{\prime }$ and $a_i^{\prime \prime }$. The contraction has $n-1$ vertices, so subtracting its polynomial changes its leading sign by one place. Thuswith nonexistent indices understood as zero. Both summands are nonnegative by induction. The leading coefficient is $a_0=1$, and the next isThis proves the alternating expansion and nonnegativity of every $a_i$. The coefficient assertion for $a_1$ is relevant when $n\ge 2$; the one-vertex graph simply has polynomial $x$.

Set $t=-x>0$. The coefficient formula givesEvery summand is nonnegative and the leading term is $t^n>0$, since $a_0=1$. Therefore

For the complete graph, $p_{K_n}(x)=x(x-1)\cdots (x-n+1)>0$ whenever $x>n-1$.

Use induction on the number of vertices, and for fixed $n$ on the number of missing edges. If $G$ is not complete, choose a missing edge $e$ and put $H=G+e$. The recurrence rearranges asThe first term is positive by the missing-edge induction. The second graph has $n-1$ vertices, so the vertex induction makes its polynomial positive for $x>n-2$, in particular for the present range. The one-vertex base case is $x>0$. Thus $p_G(x)>0$ for all $x>n-1$, including noninteger $x$; counting colorings alone would not establish that real-variable claim.

For disjoint nonempty vertex sets, their edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is epsilon-regular or epsilon-uniform if for all $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$,It controls density on every sufficiently large subpair, rather than merely on average over chosen subpairs.

An epsilon-uniform partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering the vertex set, with $|V_0|\le ϵ|V(G)|$, equal nonexceptional class sizes $|V_1|=\cdots =|V_k|$, and at most $ϵk^2$ unordered pairs of distinct nonexceptional classes failing epsilon-uniformity. The exceptional set need not have the common size.

Szemerédi regularity lemma states that for every $ϵ>0$ and positive integer $m_0$, there is $M=M(ϵ,m_0)$ such that every sufficiently large finite graph, for example every graph of order at least $M$ after enlarging $M$ if needed, has such a partition with $m_0\le k\le M$. The bound depends only on the accuracy and minimum class count, not on the graph's order.

Let $S\subseteq X$ be the vertices with fewer than $dn/2$ neighbours in $Y$. If $|S|>ϵn$, its density to all of $Y$ is below $d/2$. But epsilon-uniformity applies to $(S,Y)$ and requiresa contradiction. Therefore $|S|\le ϵn$.

Apply part (c) to the pairs $(X_1,X_2)$ and $(X_1,X_3)$. Outside a union of at most $2ϵn$ exceptional vertices, every $v\in X_1$ has sets $Y=N(v)\cap X_2$ and $Z=N(v)\cap X_3$ of size at least $dn/2$.

These sets are large enough for epsilon-uniformity of $(X_2,X_3)$, because $d/2>ϵ$. HenceEvery such edge completes a distinct triangle through $v$. Thus at most $2ϵn$ vertices of $X_1$ fail the claimed triangle count. Summing these triangles over the good vertices counts each triangle with one vertex in each class exactly once. Since $d\le 1$ and $ϵ<d/4\le 1/4$,