vertex covering number

224 Views Asked by At

I want to find $\alpha(G)$ that is vertex independence number(maximum number of vertices, no two of which are adjacent) and $\beta(G)$ that is edge covering number(minimum number of vertices that cover all edges of G) of this graph: enter image description here

I've found that $\alpha(G)=2$. And there is theorem that says: $\alpha(G)+\beta(G)=n$. So $\beta(G)$ must be $4$. But I can't find $4$ vertices that cover all edges of G. Would you please help?

1

There are 1 best solutions below

0
On

Let $G$ be a simple graph with $n$ vertices. Suppose $A$ is a set of independent vertices. Then the set of vertices not in $A$ (which we will denote $A'$) covers the edges.

Proof:

Any edge has two vertices, at most one of which can lie in $A$ (as $A$ independent), so at least one of which will lie in $A'$. $\hspace{17cm} \Box$

In your case, you just need to pick any independent pair of vertices in your graph, and the remaining four vertices will cover the edges.


Note the other direction holds too:

Suppose $B$ is a set of vertices which covers the edges. Then the set of vertices not in $B$ (which we will denote $B'$) is independent.

Proof:

Any edge has two vertices, at least one of which will lie in $B$ (as $B$ covers the edges), so the edge cannot link two vertices of $B'$. $\hspace{17cm} \Box$

Consider partitions of the $n$ vertices into sets $A,B$ with $A$ independent and $B$ covering the edges. Then the above results tell us that every independent set arises as a set $A$ in this way. Similarly every set which covers the edges arises as a set $B$ in this way. Now as $|A|+|B|=n$, we see that $|A|$ maximises when $|B|$ minimises, and in this case as always $|A|+|B|=n$, proving the theorem you mentioned.

It is often the case that understanding the steps in the proof a theorem, can help with related calculations, as well as the statement of the theorem itself.