# Must the largest independent set of a graph contain a vertex of minimum degree?

Must the largest independent set of a graph contain a vertex of minimum degree?

My gut feeling is yes, but I can't think of a substantive reason as to why. Does a proof for this exist, or is this premise false?

• The question itself is good, but you could improve your post by including context. – 6005 Dec 8 '16 at 7:13
• Do you mean every maximum independent set? I think that might not be true. But, if true, would be an interesting result. – Joffan Dec 8 '16 at 7:28

Consider the following graph

The maximum independent set size of this graph is three, since an independent set can contain at most one of A and B, of D and E, and of C, F and G. The set {B, F, D} is a maximum independent set without any vertices of minimal degree.

Edit: I saw Bof's answer and realized it's better than mine, since for this example, there are no maximum independent sets that contain vertices of minimal degree. Here is a picture of Bof's solution.

• Thank you! That's a very simple example that I didn't think of. – user203167 Dec 8 '16 at 16:32

Here is an example of a graph in which no largest independent set contains a vertex of minimum degree.

The graph $G$ has $7$ vertices $t,u,v,w,x,y,z$ and $14$ edges; namely, there are edges joining the vertices $x,y,z$ to one another; edges joining each of the vertices $u,v,w$ to each of the vertices $x,y,z;$ and edges $tu,tv.$ The minimum degree is $2,$ and the independence number is $3.$ The vertex $t$ is the only vertex of degree $2,$ and the set $\{u,v,w\}$ is the only independent set of cardinality $3.$

• Interesting construction – Joffan Dec 8 '16 at 15:24
• Great solution - the original question was ambiguous, but this counterexample covers both interpretations. – Bolton Bailey Dec 12 '16 at 3:49