The problem described in the title comes from my previous question:
I think it is necessary to take it as a new problem.
For bipartite graphs, as koifish proved in the answer, the following statement is true.
Theorem 1. Let $G$ be a bipartite graph. Then $\kappa(G) \le \alpha'(G)$.
If we remove the "bipartitity" in Theorem 1, we'll find some counterexamples.
The simplest example is found by kabenyuk:
- The triangle is a 2-connected graph, but its matching number is 1.
And then I found some other examples.
-
the complete graph $K_4$ ($3=\kappa(K_4)> \alpha'(K_4)=2$).
-
The following graphs satisfy that $\kappa(G) > \alpha'(G)$.
So I thought of the following question.
Question. Given an arbitrary vertex connectivity $\kappa$, is there a graph that satisfies $\kappa(G) > \alpha'(G)$？
Maybe we need to find a way to construct such graphs.
Edits: I was just reminded by kabenyuk that complete graphs are sufficient to solve this problem. It is. The matching number for any graph with $n$ vertices is at most $\lfloor \frac{n}{2} \rfloor$. But the vertex connectivity can be much larger than $\frac{n}{2}$.
So a better problem is to characterize which non-bipartite graphs satisfy the inequality $\kappa> \alpha'$.
Ps:
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 $α′(G)$ of graph $G$, sometimes known as the edge independence
number, is the size of a maximum independent edge set.
Best Answer
We can prove the following theorem, which tells us considerably more about such graphs:
Theorem. If $\kappa(G) > \alpha'(G)$, then $\alpha'(G) = \lfloor \frac n2 \rfloor$: a maximum matching leaves at most one vertex of $G$ unmatched.
Proof. Suppose $\alpha'(G) = \frac{n-k}{2}$, so that a maximum matching has $k$ unmatched vertices, and that $k \ge 2$. Then by the Tutte–Berge formula there is a set of vertices $U$ such that $G-U$ has $|U|+k$ odd components. This is, in particular, multiple odd components: so $\kappa(G) \le |U|$, because $G-U$ is not connected. Also, $G-U$ must have at least $|U|+k$ vertices, so $n-|U| \ge |U|+k$, or $|U| \le \frac{n-k}{2}$. In summary, $$\kappa(G) \le |U| \le \frac{n-k}{2} = \alpha'(G).$$ Therefore if $\kappa(G) > \alpha'(G)$, then $k \le 1$ and so $\alpha'(G) \ge \frac{n-1}{2}$.
In fact, we don't need as strong an inequality as $\kappa(G) > \alpha'(G)$: if $\kappa'(G) > \alpha'(G)$, or even if $\delta(G) > \alpha'(G)$, then we can already conclude that $\alpha'(G) = \lfloor \frac n2 \rfloor$.
For this, we use the Tutte–Berge formula more carefully. As before, suppose $\alpha'(G) = \frac{n-k}{2}$ with $k\ge 2$, and take any set of vertices $U$ such that $G-U$ has $|U|+k$ odd components. Now, additionally, let the smallest odd component have $2j+1$ vertices.
Then $$\alpha'(G) = \frac{n-k}{2} \ge \frac{|U|+(2j+1)(|U|+k)-k}{2} = (j+1)|U| + jk$$ whereas $\delta(G) \le |U|+2j$: this is the maximum possible degree of a vertex in the smallest odd component. The inequality $\delta(G) > \alpha'(G)$ rearranges to $j(|U|+k-2) < 0$, contradicting our initial assumption that $k \ge 2$.
This is not a characterization, but I think that there will be no good description beyond this. For example, if you take a random $n$-vertex graph with edge probability $\frac12 + \epsilon$, then with high probability $\alpha'(G) = \lfloor \frac n2 \rfloor$ and $\kappa(G) = \kappa'(G) = \delta(G) \approx (\frac12 + \epsilon)n$. This gives lots and lots of boring examples.