Graph Theory
Lessons
Lesson
4: Complete Graphs, SubgraphsA complete graph
is a graph where every pair of distinct vertices are adjacent.
A complete graph on n vertices is denoted by Kn
(or sometimes by K(n) ). So, for example, figure 6 is the graph
K5.
|
| Fig. 6, The Graph K5 |
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 6. Take a look at some others like K3, K8, K17 etc.
In graphs with many edges like K17 it is hard to see the labels. Click on Picture and Linewidth. Set the linewidth to 0. You will get a small rectangle and notice that within the rectangle the edges are not drawn so you can move it around to see which vertex is where. When you are done set the linewidth back to 1.
We say that a graph G1 is a subgraph
of a graph G2 if G1 is isomorphic to
a graph all of whose vertices and edges are in G2. Note that
by our definition a graph is always a subgraph of itself. The applet below will
help you to understand the concept. Draw graphs in the two windows in the
same way as you have done in previous applets. If the graph of the left is
a subgraph of the graph on the right you will see its isomorphic image drawn
in red in the graph on the right.
For large graphs it is better to use the Petersen program. How do we check if one graph is a subgraph of another using Petersen? Start the program and let us check if K4 is a subgraph of K5. Get K4 (Click Graph then Complete then Complete Graph and enter 4 when you are asked the number of vertices) and save it as graph 2. Now get K5 and click Relations and then Find Subgraph. You will get a new window like you did in lesson 3 with two picture boxes. Click on Start. You will get a list of the graphs currently saved as graphs 1 to 20. K4 should be in the second position. Click on K4. Now the text box should say that there is an isomorphic subgraph. Click on Morph and you will get some animation. When you are done click Done.
