Understanding a Graph Theory Proof

[Mr Davis 97]

Prove that if a simple graph G has 6 vertices then G or its complement has a subgraph isomorphic to $K_3$.

The proof begins by noting that is must be the case that G or its complement as a vertex with degree at least 3. Why is this the case?

 

[mfb]

Pick a random vertex. If its degree is 3 or more you are done. If its degree is smaller, what is the degree of the vertex for the complement?

 

[Mr Davis 97]

Pick a random vertex. If its degree is 3 or more you are done. If its degree is smaller, what is the degree of the vertex for the complement?

I got it now. How would this result generalize? Would it be correct to say that G or its complement must have a vertex with degree at least $\lfloor v/2 \rfloor$?

 

[mfb]

Sure.