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.
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.
- What is the complement of the complete graph Kn?
- 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.
- What is the complement of the complete tripartite graph Kr, s, t?
In the Petersen program, get the
by using the menu item Graph | Named Graph | Bull.
Fig 37.3, The bull graph
- 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.
- Prove that if a self-complementary graph has 4n+1 vertices then at least one of the vertices has degree 2n.
- 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]
- For what value(s) of n greater than 1 is the circuit Cn isomorphic to its complement?
- 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.]
- Does the complement of the Petersen graph have an Euler Circuit ?
- Suppose a graph G on n vertices, n odd, has an Euler circuit. Does its complement ~G, if connected, have an Euler circuit?
- Suppose a graph G on n vertices, n even, has an Euler circuit. Does its complement ~G, if connected, have an Euler circuit?
- Get the circuit C5 and store it in favorites by clicking Graph | Add to Favorites.
- Find its complement ~C5 and store that too in favorites.
- 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
- 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.
- In a similar fashion get the sum C5 + S7, and then its complement ~(C5 + S7). Does the graph look familiar?
- Just to be sure, click Relations | Isomorphism. Now click Graph | Favorites and get ~C5 U ~S7. Are the two graphs isomorphic?
- In general how is ~(G1+G2) related to ~G1 and ~G2?
- Prove that if I is an independent set in G then it is a clique in the complement ~G.
- Prove that for any graph G, the clique number of G is equal to the independence number of the complement of G.
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.
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].
© C. Mawata