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 [inline]G[/inline] has more than [inline]4[/inline] vertices then [inline]G[/inline] 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 [inline]G[/inline] is isomorphic with [inline]\overline{G}[/inline]) has [inline]4n[/inline] or [inline]4n + 1[/inline] 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 [inline]3[/inline] or more. Such a vertex must be connected to [inline]3[/inline] other vertices. Show that no matter what edges you place amongst those [inline]3[/inline] 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.

Add Your Message Here
Posting is currently disabled in this topic. Contact your discussion moderator for more information.

Topics | Last Day | Last Week | Tree View | Search | Help/Instructions | Program Credits Administration