Minimum size of cut-vertex set Consider a bipartite graph $G$ with bipartition $(X,Y)$. A new graph $G^{'}$ is created by adding two vertices $s$ and $t$ such that $s$ is connected to all vertices in $X$ and $t$ is connected to all vertices in $Y$. What is the minimum size of a vertex set that disconnects $s$ and $t$?
Is it the minimum size of vertex cover of $G$?
 A: The minimum size of a vertex set that disconnects s and t in $G'$ is $\nu(G)$, the size of a maximum matching in $G$. Divide the vertices of $X$ and $Y$ into two parts each, those vertices that are in the matching ($X_0$ and $Y_0$) and those that are not ($X_1$ and $Y_1$):
         s
    /---------\
X_0 ooo...ooo o X_1
    |||.M.|||×
Y_0 ooo...ooo ooo Y_1
    \-----------/
          t

Because the matching $M$ is maximal, there cannot be any edges between $X_1$ and $Y_1$, though there may be edges between $X_0$ and $Y_1$ or between $Y_0$ and $X_1$. Deleting $X_0$ disconnects s and t, because that leaves no edges connecting $X$ and $Y$; similarly, deleting $Y_0$ disconnects s and t, and $\nu(G)$ is an upper bound on the order of the desired minimal cut-vertex set. $\nu(G)$ is also a lower bound, because cutting less than that number of vertices must preserve at least one edge in $M$ and hence a path from s to t.
We have thus proved rigorously that the answer to the question is $\nu(G)$. Since $G$ is bipartite, by Kőnig's theorem $\nu(G)$ is also the size of the minimum vertex cover of $G$.
