**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. |