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

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.