Show that the only regular, self-complementary, planar graph is the 5-cycle. Pay special attention to the 4-regular case.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.