Find a graph with 5 vertices such that $\omega(G) = 2$ and $\alpha(G) = 2$.

287 Views Asked by At

I am trying to show that the following statement is false by providing a drawn graph as a counterexample. I've been pointed in the right direction that the statement is only true for at least 6 vertices, so I know it can be disproved. Please correct me if I am wrong though!

If you have any input other than a picture as to why this is false, please share that too!

If $G$ is a graph with at least 5 vertices, then $\omega(G) \ge 3$ or $\alpha(G) \ge 3$.

However, I'm having trouble finding an independence number of 2. Every graph I've drawn on paper seems to turn out to have an independence number of 3 and a clique number of 2.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider a pentagon. It satisfies $\alpha(G)=\omega(G)=2$.