Let $G$ be a connected graph with $2p$ vertices.
We want to show that $$\frac{|VertexCover|_{min}}{|MaximalMatching|}<2$$
I started like this :
Let $G$ be a graph with $2p$ vertices such that $\frac{|VertexCover|_{min}}{|MaximalMatching|}=2$.
Suppose $X$ a maximal matching of size $m$. Let $VC$ be the set of all vertices that appear in X. We can easily show that $VC$ is a vertex cover and $VC$ is of size $2m$. Since the ratio is equal to 2, $VC$ must be a minimal vertex cover.
I wanted to show that we can remove at least one vertice from $VC$ and still keep a vertex cover but I failed to do that.
Can anyone provide some help ? Is this even the correct approach for this question ?
Thanks.
If there is a maximal alternating path $P$, alternating between edges in $X$ and edges not in $X$ starting and ending with edges not in $X$(alternating path is a path such that if you traverse along the path, you go through an edge in $X$ and then an edge not in $X$ and then an edge in $X$ and so on), then you could increase the size of $X$(By replacing $E(P)\cap X$ with $E(P) \cap (E(G)-X)$). Therefore, either a maximal alternating path start with an edge in $X$ and ends with an edge not in $X$ or starts and ends with edges in $X$. In the both cases, we can remove the end vertex of the path $P$ with is incident the the edge in $X$ to create a smaller vertex cover.
For example, in the following graph:
$X$ are the edges labeled $1$ and $VC=\{3,2,6,1,0,5,7,8\}$. we see an alternating path from node $4$ to node $8$ in zigzag. The path ends with an edge in $X$. so we can remove node $8$. So here we didn't use that fact that $G$ has $2p$ vertices. So there could be something missing... Is this correct?