Draw a regular graph on 8 vertices such that it does not have a K3 , and has no independent set of cardinality 4.

Question

Draw a regular graph(one which has all vertices of equal degree) on 8 vertices such that it does not have a triangle and has no independent set of cardinality 4.

I'm wondering if this is even possible? I've tried various graphs but this seems impossible. But how do I constructively prove this that it cannot be done?

Answer 1

The following graph has neither $K_3$ nor an independent set of size 4:

We take an 8-cycle, in which the biggest independent set has size at most 4, and make two vertices of each maximal independent set adjacent.

Answer 2

Let $G$ be a $d$-regular graph on $8$ vertices that is triangle-free and has an independent set of size $4$.

1. For $d=0$ the edgeless graph on $8$ vertices is the only example.
2. For $d=1$ there is clearly also just one example.
3. For $d=2$ the $8$-cycle is an example, as is the union of two $4$-cycles.
4. For $d=3$ the cube graph is an example.
5. For $d=4$ the bipartite graph $K_{4,4}$ is an example.

For $d\geq5$ clearly $G$ cannot contain an independent set of cardinality $4$.