in Combinatory edited by
1,340 views
1 vote
1 vote
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.
in Combinatory edited by
1.3k views

1 Answer

1 vote
1 vote
Best answer

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.

selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true