29.2.5. Self-complementary Graph

Try these first

1. 1.

   Define a self-complementary graph.

   Hint

   Think about the relationship between a graph and its complement.

2. 2.

   Provide an example of a self-complementary graph.

   Hint

   Consider small complete graphs.

3. 3.

   What defines a self-complementary graph?

   • It has more vertices than edges
   • It's isomorphic to its complement
   • It contains cycles

   Hint

   Focus on the definition of isomorphic graphs.

4. 4.

   True or False: A graph with 7 vertices can be self-complementary.

   • True
   • False

   Hint

   Think about the remainder when dividing 7 by 4.

5. 5.

   Construct a self-complementary graph with 12 vertices. Illustrate how you grouped the vertices and the connections made.

   Hint

   Remember to connect completely within some groups and leave some connections absent for others.

6. 6.

   Prove that a graph cannot be self-complementary if it has an odd number of vertices.

   Hint

   Examine how edges are counted in both graphs.