Maximal independent sets in regular graphs?

Question

Suppose we have an $r-regular$ graph $G$, with vertex set $V$. For $v \in V$ let $I(v)$ denoted an independent set, which is of a maximal size, such that it contains $v$. Is is true that $\forall u,v \in V$ $I(v)$ is the same size as $I(u)$ ??? I believe that it must be true, because in a regular graph, every vertex has the same number of non-adjacent vertices, and an independent set is just a collection of mutually non-adjacent vertices.

Answer 1

This is false; a counterexample is given below.

The independence number of this graph is $4$, with an independent set highlighted. In fact, this is the unique independent set of size $4$, which can be checked with some casework:

• If we include one of the middle vertices of the left or right "diamond", we can't include any other vertices of that diamond.
• So if we include a middle vertex of both diamonds, we are left with only the two vertices down the center to finish with, which are adjacent; so we can only get an independent set of size $3$.
• If we include a middle vertex of only the left diamond (without loss of generality, then we are left with the two vertices down the center and the top and bottom vertices of the right diamond. We can pick at most two of these, so we can also only get an independent set of size $3$.
• If we include no middle vertices of either diamond, we have two paths of length $3$ left, and the only way to get an independent set of size $4$ is to pick both endpoints of both paths.

So we'll have $|I(v)| = 4$ for the highlighted vertices of the graph, and $|I(v)| = 3$ for all the other vertices.