Pigeonhole Principle (2)

Question

Suppose a graph $G$ has $6$ nodes. Prove that either $G$ or $G'$ must contain a triangle.

($G'$ is the complement of $G$.) Prove it using pigeonhole principle.

Answer 1

Let us assume A,B,C,D,E,F be 6 vertices in the graph G.  Choose any vertex A in the graph G .Now, by pigeon hole principle we will get one of G or G' would contain at least 3 edges from A .

WLOG assume that the graph G contains at least 3 edges from A suppose the three edges be AB,AC,AD.  

Now, if the edge BC belongs to G then the triangle ABC belongs to G.

if the edge CD belongs to G then the triangle ACD belongs to G

if the edge BD belongs to G then the triangle ABD belongs to G.

Now, if none of the edges BC , CD, BD belongs to G then the triangle BCD belongs to G.

In any way we have a triangle belongs to either G or G'

So, one of G or G' must contain a triangle.