Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 3 / 17H (Graph Theory)

Hall marriage theorem says that a bipartite graph with equal finite vertex-class sizes has a perfect matching exactly when $|\Gamma (A)|\ge |A|$ for every $A\subseteq X$. Necessity follows because distinct matched partners of vertices of $A$ belong to $\Gamma (A)$.

For sufficiency, induct on $n$, the case $n=1$ being immediate. If a nonempty proper $A$ is tight, $|\Gamma (A)|=|A|$, the induced graph between $A$ and $\Gamma (A)$ satisfies Hall's condition and has a matching by induction. The remaining graph also satisfies it: for $B\subseteq X\setminus A$, the condition on $A\cup B$ gives $|\Gamma (B)\setminus \Gamma (A)|\ge |B|$. Induction gives the second matching, and their union is perfect. Otherwise every nonempty proper subset has strictly more neighbours. Choose an edge $xy$ and remove its ends. Every remaining nonempty subset loses at most one neighbour and originally had at least one spare neighbour, so Hall's condition survives. Induction matches the remaining graph, and restoring $xy$ completes the proof.

The last argument also proves flexibility under the strict condition: it works for every selected edge, so every vertex is flexible. The case $n=1$ is again immediate.

Now suppose only that a perfect matching exists. Choose a minimal nonempty tight set $A\subseteq X$; such a set exists since $X$ is tight. Every nonempty proper subset of $A$ satisfies the strict condition in the induced graph on $A,\Gamma (A)$. Hence every edge from a vertex of $A$ extends to a matching of that induced graph. There are no edges from $A$ to the complement of $\Gamma (A)$. Restrict the original perfect matching to the complementary vertex classes and append it to this new induced matching. This makes every vertex of $A$ flexible in the whole graph, proving that at least one flexible vertex exists.

For the requested counterexample, take $X=\{x_1,x_2,x_3,x_4\}$ and $Y=\{y_1,y_2,y_3,y_4\}$. Join $x_1$ only to $y_1,y_2$, and join each of $x_2,x_3,x_4$ to all of $y_2,y_3,y_4$. There is a perfect matching using $x_1{y}_1$ and a matching of the remaining complete bipartite graph. The unique minimum-degree vertex is $x_1$, of degree two, but $x_1{y}_2$ cannot occur in a perfect matching because $y_1$ has no other neighbour. Thus no minimum-degree vertex is flexible, while the other three vertices are flexible.