# Minimal vertex cover

Definition: Let $$G$$ be a graph. A subset $$C \subseteq V(G)$$ is a vertex cover of $$G$$ if for each $$e \in E(G)$$, $$e\cap C \neq \phi$$. If $$C$$ is minimal with respect to inclusion, then $$C$$ is called minimal vertex cover of $$G$$.

Let $$G$$ be a graph with $$V(G)=\{z_1,\ldots,z_n\}$$. Let $$H$$ be the new graph $$H$$ on new vertices $$\{z_{1,1},z_{1,2},\ldots ,z_{n,1},z_{n,2}\}$$ and edge set of $$H$$ be $$E(G)=\Big\{ \{z_{a,b},z_{c,d}\} \mid \{z_{a},z_c\} \in E(G) \text{ and } b+d \leq 3\Big\}$$.

One can see that if $$M_1=\{z_{i_1},\ldots,z_{i_r}\}$$ is a minimal vertex cover of $$G$$ , then $$M_2=\{z_{i_1,1},z_{i_1,2},\ldots,z_{i_r,1},z_{i_r,2}\}$$ is a minimal vertex cover of $$H$$.

Is $$M_2$$ the largest cardinality of minimal vertex cover of $$H$$?

Not necessarily. E.g., the set $$\{z_{i,1}\colon 1\leq i\leq n\}$$ is also a minimal vertex cover of $$H$$ (whenever $$G$$ has no isolated vertices), and it may have more elements (e.g., if $$G$$ is a star, and $$M_1$$ consists of its center).

In fact, all minimal covers of $$H$$ can be pbtained in the following way. Notice that, if $$C_2$$ is a cover of $$H$$, then $$C_1=\{z_i\colon z_{i,1}\in C_2\}$$ is necessarily a cover of $$G$$. So, let us start with a (not necesarily minimal) cover $$C_1$$ of $$G$$, and include into a sought cover $$C_2$$ of $$H$$ all vertices $$z_{i,1}$$ with $$z_i\in C_1$$. We need also to include all $$z_{j,2}$$ which are neighbours of some $$z_{k,1}$$ with $$z_k\notin C_1$$.

This constitutes a cover of $$H$$, but not necessarily a minimal one. Say that a vertex in a covering is necessary if it cannot be removed. Then all vertices $$z_{j,2}\in C_2$$ are necessary, as well as all vertices corresponding to necessary vertices of $$C_1$$. On the other hand, a vertex of $$C_2$$corresponding to unnecessary vertex in $$C_1$$ is necessary if it has a neighbor $$z_{j,2}$$ which is not in $$C_2$$; that neighbor coresponds to another unnecessary neighbor in $$C_1$$.

Thus, the condition that $$C_2$$ is monomal is; Each unnecessary vertex in $$C_1$$ has an unnecessary neighbor.

[EDIT OF ADDENDUM] Sorry, the previous argument was wrong. It showed only that the conjecture from the comment holds whenever each induced subgraph of $$G$$ has a minimal vertex cover containing at least half of its vertices. However, there exist graphs where each minimal vertex cover has less than a half of vertices, and each such graph is a counterexample to what you wanted.

E.g., take $$K_3$$, and attach to each its vertex two degree 1 vertices (so we have 9 vertices at all). Each its minimal vertex cover contains two vertices of $$K_3$$, hence it contains either the third vertex as well, or two its leaves. Hence $$M_1$$ may contain at most 4 vertices. On the other hand, the graph $$H$$ admits a minimal vertex cover of 9 vertices, as described above.

• Suppose $M_1$ is the largest minimal vertex cover of $G$. Is $M_2$ the largest minimal vertex cover of $H$? – user177523 Nov 18 '18 at 9:08
• Added an answer; hope this is the last reformulation;). – Ilya Bogdanov Nov 18 '18 at 10:00
• Sorry, the previous addendum was wrong. I've replaced it with a (more) correct one. – Ilya Bogdanov Nov 18 '18 at 20:07