If $G$ is $k$-connected graph, has no perfect matching and is not factor-critical, then $\nu(G) \geq k$ and $\tau(G) \leq 2 \nu(G) -k$

Question

Question: If $G$ is $k$-connected graph, has no perfect matching and is not factor-critical, then $\nu(G) \geq k$ and $\tau(G) \leq 2 \nu(G) -k$

Hint: use the Edmonds-Gallai decomposition.

$\nu(G)$ is the size of the maximum matching.

$\tau(G)$ is the size of the minimum vertex cover.

A graph $G$ is $k$-connected if:

1. $|V(G)| > k$;
2. $V(G)-X$ is connected for all $X \subseteq V(G)$ with $|X| < k$

Perfect matching is a matching that covers every vertex of the graph.

A graph is factor-critical if every subgraph with $n-1$ vertices has a perfect matching.

A connected graph is factor-critical if and only if every vertex of the graph is inessential. A essencial vertex is a vertex that is present in every maximum matching of the graph. A inessencial vertex is a vertex that is not essencial.

What i've have thinking In a $k$-connected graph the minimum degree is equal to $k$ (otherwise we could pick a vertex $v$ with less then $k$ neighboors, delet them, and then made the graph disconnected. So, pick a vertex that is not covered by some maximum matching. This vertex exists, since $G$ has no perfect matching. Every neighbor of this vertex is covered by the matching; otherwise we could pick the edge between $v$ and a neighbor not covered by the matching and increase the maximum matching, contradiction. So $\nu(G) \geq \frac{k}{2}$.

The hint is to use the Edmonds-Gallai decomposition. But i'm no sure to how use this to prove that every neighbor of $v$ is matched with an vertice that is not in the neighbor of $v$, and that way proving that $\nu(G) \geq k$. I can't think of anything for the second inequality.

Answer 1

After discussing with Misha in the comments I was able to answer the question.

First, if $k = 0$, the proposition holds trivially, since $\nu(G) \geq 0$ and $\tau(G) \leq 2 \nu(G)$ for every graph $G$. So we may assume that $k \geq 1$, and in this case $G$ is connected.

First Part: Let $D$, $A$, $C$ be the following sets in the Edmonds-Gallai decomposition:

$D$ - The inessential vertices

$A$ - The essential vertices in the neighborhood of $D$

$C$ - The essential vertices that are not in the neighborhood of $A$

We know that $G$ doesn't have perfect matching and is not factor-critical, so, $G$ has at least one essential vertice and one inessential vertice. So $D \neq \emptyset$. We claim that $A \neq \emptyset$. If $A = \emptyset$ then all essential vertices are in $C$. But $C$ has no edges to $D$, so $G$ is disconnected, contradicting the fact that $G$ is $k$-connected.

We know that set $A$ of the Edmonds-Gallai decomposition satisfies the Tutte-Berge formula with equality. So, in the Tutte-Berge formula:

$$\nu(G) = \min_{X \subseteq V(G)} \frac{1}{2}(|V(G)| - (\mathrm{odd}(G-X) - |X|)) $$

if we take $X=A$ we have:

$$\nu(G) = \frac{1}{2}(|V(G)| - (\mathrm{odd}(G-A) - |A|)) $$

$G$ doesn't have perfect matching and $A$ is not empty, so $\mathrm{odd}(G-A) - |A| > 0 \Rightarrow \mathrm{odd}(G-A) > |A| \geq 1$, and then $\mathrm{odd}(G-A) \geq 2$. Therefore, deleting $A$ leaves at least two disconnected components. Since $G$ is $k$-connected, $|A| \geq k$, and since $A$ is a set of essential vertices, we have $\nu(G) \geq k$.

Second Part: We know that the set $D$ in the Edmonds-Gallai decomposition is precisely the odd components in $G-A$. Consider the following set: All vertices in $G$ minus one vertice $v$ from each odd component in $G-A$, with $v$ being a vertex with at least one neighbor in $A$. We claim this is a vertex cover. Since each $v$ are in an odd component of $G-A$, they are all inessencial, and $v \in D$. The only edges that might not be covered are the ones with one endpoint being $v$. The edges the $v$ has with $A$ are covered by the vertices of $A$, and the edges the $v$ has inside his odd component are covered by all the other vertices in this component, which are in our set. So this set is a vertex cover of size $|V(G)| - \mathrm{odd}(G-A)$. Since $A \geq k$ we have:

\begin{align*} \tau(G) &\leq |V(G)| - \mathrm{odd}(G-A) \\ &= |V(G)| - \mathrm{odd}(G-A) + |A| - |A| \\ &\leq (|V(G)| - \mathrm{odd}(G-A) + |A|) - k \\ &\leq 2\nu(G) - k \\ \end{align*}