So we proved the following version of Menger: Let G be a graph and S, T be two subsets of the vertex set of G.

Then the maximum number of vertex-disjoint ST-paths is equal to the minimum cardinality of an ST-cut

Here vertex disjoint means the paths are disjoint at ALL vertices and the ST-cut is allowed to intersect with S and T

We prove a refined version:

Let G be a graph and s, t in G be two non-adjacent vertices. Then the minimum cardinality of an st-cut not containing s or t is equal to max cardinality of a collection of internally (so allowed to intersect at endpoints) disjoint st-paths

Proof: Let S = N(s) and T = N(t) be the neighborhoods of s and t respectively

Using Menger, min ST-cut is equal to max vertex disjoint ST-paths

Claim: min ST-cut = min st-cut.

Argument: If there exists st-path that does not hit min ST-cut, then take penultimate endpoints of the path to get ST-path not hitting min ST-cut, contradiction.

Corollary: G is k-connected iff there exists k internally disjoint paths between any two points in G

(Sorry I was guiding a friend through the proof of this theorem, spamming a little more than usual hence)

Fun fact: For k = 2 the above theorem is by Hassler Whitney

Let $G$ be a graph. A matching is a subset $M \subset E(G)$ such that every pair of edges intersect trivially, size of max matching is $\nu(G)$. A set of vertices $T \subset V(G)$ is called a cover if every edge has some endpoint in $T$, size of min cover is $\tau(G)$.

Theorem (Konig): $\tau(G) = \nu(G)$

Proof: Observe first that $\nu(G) \leq \tau(G)$. This is because, given a matching and a cover, every edge of the matching must contain some vertex of the cover, hence matchings always have cardinality less than vertex covers. Take max and min on respective sides to get the inequality.

Oh I mis-stated the theorem. If $G$ is a bipartite graph, $\tau(G) = \nu(G)$. Sorry.

OK, let $U$ be a min vertex cover of our bipartite $G = A \cup B$. Consider the subgraph $H$ induced by $A \cap U$ and $B \setminus (B \cap U)$, and the subgraph $H'$ induced by $A \setminus (A \cap U)$ and $B \cap U$.

Note that $G$ has no edges from $A \setminus (A \cap U)$ to $B \setminus (B \cap U)$, because such an edge would avoid $U$ completely, but $U$ is a vertex cover.

Let $S \subset A \cap U$ be a subset of vertices. The set of neighbors $N_H(S)$ of $S$ in $H$ forms a subset of $B \setminus (B \cap U)$. If $|N_H(S)| < |S|$, then $(U \setminus S) \cup N_H(S)$ is a smaller vertex cover of $G$ I think.

If we had an edge landing into a non-$S$ vertex of $U$, it still lands into that vertex surviving in $(U \setminus S) \cup N_H(S)$. If we had an edge landing into a $S$ vertex of $U$, it lands into $N_H(S)$ hence $(U \setminus S) \cup N_H(S)$

So this is a contradiction, $|N_H(S)| \geq |S|$ for all $S \subset A \cap U$. So $H$ satisfies Hall's marriage condition, so $H$ has a matching covering all of $A \cap U$

$H'$ similarly also has a matching covering all of $B \cap U$. Adding these togather we get a matching of cardinality $|U|$.

There should be a direct argument for this; let's see. Take a maximal matching $M$ and assume it doesn't cover all of $A$. Take $a_0 \in A \setminus M$.

$N(a_0)$ contains at least one point $b_0$, and if it's not already part of the matching $M$, we can add the edge $(a_0, b_0)$ to $M$ contradicting maximality.

So $b_0$ is part of the matching, so has a neighbor $a_1 \in A \cap M$ (I'm being flippant with notation here but you get what I mean).

$N(a_0, a_1)$ has at least two points, so there's some $b_1 \neq b_0$ in $B$ which is adjacent to either $a_0$ or $a_1$.

Hm, how to proceed.

Actually you can argue $b_1$ must also be matched to something. Suppose not. We know $b_1$ is adjacent to either $a_0$ or $a_1$; in the first case we're done by adding $(a_0, b_1)$. In the second case, we have $(a_1, b_0) \in M$ already. But consider deleting this edge from $M$, and adding back $(a_0, b_0)$ and $(a_1, b_1)$ to $M$. This gives a matching bigger than $M$, contradiction.

Also observe $b_1$ is not matched to $a_1$, because that's already matched to $b_0$. So it's genuinely matched to some $a_2 \neq a_0, a_1$ in $A \cap M$.

So iteratively we find points $a_0, \cdots, a_k$ and $b_0, \cdots, b_k$ such that $b_k \in N(a_0, \cdots, a_k)$ and $b_k$ is matched to $a_{k+1} \notin \{a_0, \cdots, a_k\}$.

Just to check, observe that if $b_k$ is not matched, then since $b_k \in N(a_0, \cdots, a_k)$ it is adjacent to some $a_i$, $0 \leq i \leq k$.

We already have $(a_1, b_0), (a_2, b_1), \cdots, (a_k, b_{k-1})$ in $M$.

Delete these $k$ edges and add back $(a_j, b_{\sigma(j)})$ where $\sigma : \{0, \cdots, k\} \to \{0, \cdots, k\}$ is a permutation which takes $\sigma(i) = k$. This always exists. So we have added $k + 1$ edges back

This "dematching-rematching" process gives a new matching of $G$ one edge better than $M$, contradiction. So indeed $b_k$ is matched to some $a_{k+1} \notin \{a_0, \cdots, a_k\}$.

But this process terminates after a finite stage because $G$ is a finite graph.

Done?

As in the termination is a contradiction because we're always producing a new element of $A$ through our algorithm

Which implies the maximal matching had to cover all of $A$ in the first place.