Past exam of the short options course of the University of Oxford / 2015 / 7

A tree is a nonempty connected graph with no graph cycle. A leaf of a tree is a vertex of vertex degree one. As usual in this finite graph theory problem, trees are finite; the assertion would fail for a doubly infinite graph path.

Take a longest path $v_0,v_1,\dots ,v_m$ in a tree with at least two vertices. Connectedness gives $m\ge 1$. If $v_0$ had a neighbour outside this graph path, the path could be extended, contradicting maximal length. If it had a neighbour $v_j$ with $j\ge 2$, that edge together with the segment $v_0,v_1,\dots ,v_j$ would make a graph cycle. Thus its only neighbour is $v_1$, and it is a leaf of a tree. The same argument at the other end makes $v_m$ a second, distinct leaf of a tree. Hence

Deleting a vertex and its incident edge cannot create a graph cycle, so $T\setminus v$ is acyclic. It remains to establish connectedness and nonemptiness.

Since the leaf of a tree $v$ has one neighbour, $T$ has at least two vertices, so $T\setminus v$ is nonempty. For any two remaining vertices $a,b$, take their unique simple graph path in $T$. It cannot pass through $v$: an internal vertex on such a graph path has two incident edges, whereas $v$ has vertex degree one. Neither endpoint is $v$, so the entire graph path remains after deletion. The remaining graph is connected and acyclic, givingThis includes the two-vertex case, where deletion leaves the one-vertex tree.

Here each $T_i$ is a nonempty connected subgraph of a tree, rather than a descendant-closed data-structure subtree. We prove the Helly property for connected subgraphs of a tree by mathematical induction on the number of vertices of $T$.

For a one-vertex tree, every nonempty $T_i$ contains that vertex. For a larger tree, choose a leaf of a tree $v$ using part (i), and denote its unique neighbour by $w$. If some $T_i$ consists only of $v$, the assumed pairwise intersections force every $T_j$ to contain $v$, and we are done.

Otherwise, remove $v$ from every $T_i$ that contains it, leaving all other $T_i$ unchanged. Any affected $T_i$ has at least two vertices; connectedness forces it to contain $w$ and the edge $vw$. Thus $v$ is a leaf of a tree of $T_i$, and part (ii) shows that its deletion leaves a nonempty tree. All reduced $T_i$ are therefore nonempty connected subgraphs of a tree $T\setminus v$.

They still intersect pairwise. An original common vertex other than $v$ survives. If a pair had only $v$ in common, both members would also contain $w$, by the previous paragraph, contradicting that it was their only common vertex. The induction hypothesis now supplies a common vertex of the reduced family, which is also common to the original family. Consequently

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.

Choose a maximum matching $M$ and a minimum vertex cover $C$. By Kőnig's theorem for bipartite matching, $|M|=|C|$. Every edge of $M$ must have at least one endpoint in $C$, because $C$ is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least $|M|$ distinct vertices of $C$.

Since $C$ has exactly that many vertices, each edge of $M$ has exactly one endpoint in $C$, and no vertex of $C$ lies outside the endpoints of $M$. Thus selecting the unique endpoint in $C$ from each edge of $M$ produces precisely the vertex cover $C$:The argument also covers an edgeless graph: take both sets empty.

For every matching in a graph $M^{\prime }$ and every vertex cover $C^{\prime }$, the disjoint edges of $M^{\prime }$ need distinct covering vertices. ThereforeNow assume the assertion in part (ii). It supplies a matching in a graph $M$ and a vertex cover $C$ formed by choosing one endpoint of each edge of $M$. Because these edges are disjoint, the chosen endpoints are distinct, so $|C|=|M|$. By the definitions of maximum and minimum,Every inequality must be equality, proving Kőnig's theorem for bipartite matching: