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?

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

Consider the following graphenter image description here

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.

enter image description here

  • $\begingroup$ Thank you! That's a very simple example that I didn't think of. $\endgroup$ – 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.$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.