0
$\begingroup$

Show that the only regular, self-complementary, planar graph is the 5-cycle. Pay special attention to the 4-regular case.

1 Answers 1

1

Here's something to get you started. Let G be such a graph, with n vertices. If G is k-regular, then its complement is n-1-k-regular, so to be self-complementary, we must have k = n-1-k, so k = (n-1)/2. Now try finding a reason why the graph is nonplanar if k > 2.

  • 0
    Yeah that's the idea. But how for the 4-regular case?2010-10-24