image
Graph Theory Lessons

rule

previous index next Lesson 4: Complete Graphs

A complete graph is a graph where every vertex is adjacent to every other vertex. A complete graph on n vertices is denoted by Kn (or sometimes by K(n)). So, for example, figure 4.1 is the graph K5.

The complete graph on 5 vertices
Fig 4.1. The graph K5

Java Web Start Activity:
To get more examples of complete graphs, launch the Java Web Start application by clicking on the link below this paragraph. Once the application is running, click on the + button to increase the number of vertices. The - button decreases the number of vertices.

Java Web Start Application 4.1: Complete graphs

Petersen Activity:
To get a complete graph in the Petersen program, click Graph and then Complete Graph. You will be asked to enter the number of vertices. Enter 5, for example. You should get a graph like figure 4.2. Take a look at some others like K3, K8 and K17. We shall often refer to the graph K3 as the triangle graph or just triangle.

The triangle graph
Fig 4.2. The triangle K3

In graphs like K25 with many edges it is hard to see the details.

Complete graph on 25 vertices
Fig 4.3. The graph K25
You can get a magnification of a small region if you do the following: On the menu bar select Mouse | Magnification | x4. Now if you click on an area of the graph you will get a magnified version of that region.
Magnification of complete graph on 25 vertices
Fig 4.4. Magnification of part of the graph K25

Questions:
  1. Use the Petersen program (select Properties | Statistics on the menu) to find the number of edges in K5, K10, K20.
  2. Prove by induction that the number of edges in Kn is n(n-1)/2.
  3. Prove by using the Handshaking Lemma that the number of edges in Kn is n(n-1)/2.
  4. How many automorphisms does the complete graph on n vertices have? Justify your answer.

Answers


© C. Mawata