Some standard concepts:
- The vertex connectivity of a graph $G$, written as $κ(G)$, is the smallest number of vertices whose deletion from $G$ disconnects $G$.
- The matching number $\alpha'(G)$ of graph $G$, sometimes known as the edge independence number, is the size of a maximum independent edge set.
I see an interesting question from the following link.
This “result” implies the following assertion:
Claim. Let $G$ be a bipartite graph. Then $\kappa(G) \le \alpha'(G)$.
I see a comment of Dilettante on the post in the above link.
I am. Now I realize how easy it easy. I can just pick 1 edge from each of k independent paths, that exist by Menger's theorem.
I have a confusion about this statement. Menger theorem shows that if $G$ is $k$-connected iff for every $u,v∈V(G)$ there exist at least $k$ internally disjoint $u,v$-paths in $G$. But if there are at least two paths of length $2$ of the $k$ independent paths, the above selected scheme does not seem to say that these $k$ edges must form a matching.
So what is the correct proof of the claim?
Moreover the difinition of bipartite graphs also appears not to have been used. So my further question is:
Question. Let $G$ be a graph. Does the inequality $\kappa(G) \le \alpha'(G)$ hold?
Is there a counterexample？
Best Answer
I can answer the bipartite case for you. I do agree that the proof given in the linked question is probably not correct. For the general case, I'm not sure.
Claim. Let $G$ be bipartite with partitions $G = (A,B)$. Then $\kappa(G) \leq \alpha'(G)$.
Consider all separating sets of $G$ of cardinality $k=\kappa(G)$. Assume first that there exists a separating set $S \subseteq V(G)$ of cardinality $k$ that is not equal to one partition, ie. $S \neq A$ and $S \neq B$.
This means that in $(G - S) \cap A \neq \varnothing$ and similarly, $(G - S) \cap B \neq \varnothing$. Choose a vertex $a \in (G - S) \cap A$ and $b \in (G - S) \cap B$. Since $S$ is a separating set, $a$ is not adjacent to $b$. By Menger's theorem, there exists $k$ interally disjoint paths between $a$ and $b$. As you noted, this proof fails if there are paths with length $2$. Yet each $a-b$ path has length $\geq 3$ because $a$ and $b$ are non-adjacent and lie in different partitions.
If for instance, $S = A$, then first note that $|A| \leq |B|$, otherwise $B$ would be a separating set of cardinality $<k$. For every $s \in S$, $B \cup s$ is connected. This will imply $G$ is a complete bipartite graph. By Koning's theorem, the matching number of a bipartite graph is the size of the minimum vertex cover, and the size of the minimum vertex cover of a complete bipartite graph is the size of the smaller partition. This will give $\kappa(G) \leq \alpha'(G)$.