Vertex/Edge Independence Proof

Question

Show, for every connected graph $G$ of order $6$ with four independent vertices, that either $\alpha(G)=5$ or $\alpha'(G)\geq2$.

I was thinking about using a contradiction proof. Any hints?

Answer 1

Assume that $\alpha(G)\neq5$ and $\alpha'(G)<2$. Since $G$ is connected there are no isolated vertices and $\alpha(G)+\beta(G)=n$. Also, since $n=6$, $\beta(G)\geq5$. We know that $\alpha(G)=4$ since there are four independent vertices. Thus $n=\alpha(G)+\beta(G)\geq4+5=9$ which is a contradiction since $n=6$.

Answer 2

A lot of your hypotheses seem unnecessary. The only fact which is used is that $G$ is of order $6$. Here is a slight generalization.

Theorem: Suppose that $G$ is a graph of order $n \ge 4$. Then either $\alpha(G) = n-1$ or $\alpha'(G) \ge 2$.

Proof: If $\alpha'(G) \ge 2$ then we are done. So suppose that $\alpha'(G) = 1$. This means that every pair of edges in $G$ shares an end point. You can check that this immediately implies that $G$ is star-shaped (we require $n \ge 4$ to exclude the case of a triangle), whence $\alpha(G) = n-1$ with the points of the star as our independent set.