image Graph Theory Lessons image

rule

previous index next Lesson 37: Complements of Graphs

The complement ~G of a graph G is a graph with the same vertex set as G and with the property that two vertices are adjacent in ~G if and only if they are not adjacent in G.

Java Web Start Activity:
To see examples of graphs and their complements, launch the Java Web Start application by clicking on the link below this paragraph. Once the application is running, draw a graph in either pane. The complement of the graph will be drawn for you in the other pane. You will find the picture is less cluttered if you use only a few vertices.

Java Web Start Application 37.1: Complements of graphs

Petersen Activity:
In the questions you will need to use the Petersen program to get complements of graphs. To do that, click Operations | Complements on the menu. Try it for a few graphs of your choice.

Questions:
  1. What is the complement of the complete graph Kn?
  2. In the Petersen program, get the graph of the complete bipartite graph K2, 3. You do it by clicking Graph | Named Graph | Complete | Complete Bipartite Graph. Get the complement by clicking Operations | Complement. You should have a graph like figure 37.1.

    3. Fig 37.1, ~K2, 3

    Now move vertex 4 by dragging it with the mouse. You will find that the vertices 4, 5, and 6 form a triangle as in figure 37.2.
    Fig 37.2, ~K2, 3

    Try a few other complete bipartite graphs. After you get the complement instead of arranging the vertices manually, click Layout | Spring Layout and the program will lay the vertices out. What is the complement of Kr, s? [Hint: It is the union of two graphs].
  3. What is the complement of the complete tripartite graph Kr, s, t?
  4. In the Petersen program, get the Bull graph by using the menu item Graph | Named Graph | Bull.
    Fig 37.3, The bull graph
    What is the complement of the bull graph?
  5. When a graph is isomorphic to its complement we say it is self-complementary Prove that if a graph on n vertices is self-complementary then either n is a multiple of 4 or n-1 is a multiple of 4. Give an example of a self-complementary graph on 4 vertices.
  6. Prove that if a self-complementary graph has 4n+1 vertices then at least one of the vertices has degree 2n.
  7. If a graph with n vertices is regular of degree r, is its complement regular and if so of what degree? [Hint: Experiment with regular graphs like circuits, platonic graphs, the Petersen graph, n-cubes, complete graphs etc. until you see a pattern]
  8. For what value(s) of n greater than 1 is the circuit Cn isomorphic to its complement?
  9. What is the complement of the star Sn? [Hint: It is the union of two graphs. You might have to move vertex 1 around so as to see clearly.]
  10. Does the complement of the Petersen graph have an Euler Circuit ?
  11. Suppose a graph G on n vertices, n odd, has an Euler circuit. Does its complement ~G, if connected, have an Euler circuit?
  12. Suppose a graph G on n vertices, n even, has an Euler circuit. Does its complement ~G, if connected, have an Euler circuit?
    1. Get the circuit C5 and store it in favorites by clicking Graph | Add to Favorites.
    2. Find its complement ~C5 and store that too in favorites.
    3. Now do the same for the star on seven vertices S7 and its complement ~S7. At this point if you click Graph | Favorites you should see all four graphs in favorites
    4. Now get the union ~C5 U ~S7 as follows: Click Operations | Union. Then in the little dialog click on the menu Left Graph | Favorites and choose ~C5 by clicking on it and choosing Open Graph. Click Right Graph | Favorites and choose ~S7. You now have ~C5 U ~S7. Store the union in favorites.
    5. In a similar fashion get the sum C5 + S7, and then its complement ~(C5 + S7). Does the graph look familiar?
    6. Just to be sure, click Relations | Isomorphism. Now click Graph | Favorites and get ~C5 U ~S7. Are the two graphs isomorphic?
  14. In general how is ~(G1+G2) related to ~G1 and ~G2?
  15. Prove that if I is an independent set in G then it is a clique in the complement ~G.
  16. Prove that for any graph G, the clique number of G is equal to the independence number of the complement of G.

Answers


© C. Mawata