Show that the only regular, self-complementary, planar graph is the 5-cycle. Pay special attention to the 4-regular case.
Strange Case in Self-Complementary Planarity
0
$\begingroup$
graph-theory
1 Answers
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.
-
0Yeah that's the idea. But how for the 4-regular case? – 2010-10-24