Graph Theory Question Log Out | Topics | Search Moderators | Register | Edit Profile

 Ask NRICH » Higher Dimension » Graph Theory Question « Previous Next »

Author Message
ooonnnoooyyy
Prolific poster

Post Number: 225
 Posted on Thursday, 31 October, 2013 - 02:55 pm:

Prove that if $G$ has more than $4$ vertices then $G$ or its complement must contain a cycle.

Does anybody have hints for this question?
ooonnnoooyyy
Prolific poster

Post Number: 226
 Posted on Thursday, 31 October, 2013 - 02:58 pm:

Prove that every self-complementary graph (i.e. a graph for
which $G$ is isomorphic with $\overline{G}$) has $4n$ or $4n + 1$ points.
Daniel Fretwell
Veteran poster

Post Number: 2003
 Posted on Thursday, 31 October, 2013 - 04:12 pm:

The first is actually a very famous puzzle usually stated in the form, "show that at any part of 5 or more guests there is always a bunch of 3 people that either know each other mutually or don't".

Clearly if we prove it for any graph with 5 vertices than it follows for any more vertices by there always being a 5 vertex subgraph.

First prove that either G or its compliment must have a vertex of degree $3$ or more. Such a vertex must be connected to $3$ other vertices. Show that no matter what edges you place amongst those $3$ vertices you will either create a cycle in G or its compliment.
lebesgue
Veteran poster

Post Number: 3229
 Posted on Thursday, 31 October, 2013 - 04:24 pm:

Daniel, your advice will work with n>=6 guests, for n=5 the original question has somewhat different flavor, but it is easy then...
Daniel Fretwell
Veteran poster

Post Number: 2004
 Posted on Thursday, 31 October, 2013 - 05:48 pm:

Surely even for 5 vertices every vertex has to have degree 3 or more in either G or it's compliment?
lebesgue
Veteran poster

Post Number: 3230
 Posted on Thursday, 31 October, 2013 - 06:01 pm:

Isn't 5-cycle self-complementary?
Daniel Fretwell
Veteran poster

Post Number: 2005
 Posted on Thursday, 31 October, 2013 - 07:07 pm:

Oh I was being stupid, with n vertices the maximum vertex degree is n-1.