image Graph Theory Lessons image

rule

previous index next Lesson 26: Induced Subgraphs

We say that a graph G1 is an induced subgraph of a graph G if G1 is isomorphic to a graph whose vertex set V1 is a subset of the vertex set V of G, and whose edge set E1 consists of all the edges of G with both end vertices in V1. Note that by our definition a graph is always an induced subgraph of itself. It is important to note that not all subgraphs of a graph are induced subgraphs. We say that the graph G1 is the graph induced by the vertices V1 in G.

Java Web Start Activity:
The Java Web Start application below will help you to understand induced subgraphs. Draw graphs in the two windows in the same way as you have done in previous applications. If the graph of the left is an induced subgraph of the graph on the right you will see its isomorphic image drawn in blue in the graph on the right. If it is a subgraph but not an induced subgraph the isomorphic image will be drawn in red.

Java Web Start Application 26.1: Induced subgraphs demo

Petersen Activity:
For larger graphs it is better to use the Petersen program. How do we check if one graph is an induced subgraph of another using Petersen? Start the program and let us check if K4 is an induced subgraph of K5.

  • From the main menu, select Graph | Named Graph | Complete | Complete Graph and enter 5 when you are asked the number of vertices. You should at this point have K5 on the screen.
  • Now select from the menu bar Relations | Induced Subgraph. You should now have a new frame with two panes. The left one should be empty and the right one should have K5.
  • From the menu bar of this frame select Graph | Named Graph | Complete | Complete Graph and enter 4 when you are asked the number of vertices. You should at this point have K4 in the left pane. The text box at the bottom should describe the mapping from K4 to an isomorphic subgraph in K5.
  • Click on the button labeled Morph and you will get some animation showing how K4 would fit in K5.
    K(4) is an induced subgraph of K(5)
    Fig 26.1, K4 is an induced subgraph of K5
    Try a few other graphs to see if they are induced subgraphs of K5. When you are done select Graph | Close this Frame to get back to the original frame.
Questions:
  1. For what values of n is the complete graph Kn an induced subgraph of Km?
  2. For what values of n is the null graph Nn an induced subgraph of Nm?
  3. For what values of n is Nn an induced subgraph of Km?
  4. List all the induced subgraphs of K4.
  5. For what values of n is the null graph Nn an induced subgraph of the complete bipartite graph Kr, s?
  6. For what values of m and n is Km, n an induced subgraph of Kr, s?
  7. For what values of n is the circuit graph Cn an induced subgraph of the Petersen graph?
  8. For which values of n is the star graph Sn an induced subgraph of the wheel graph Wm?
  9. Is the relation "Is-an-induced-subgraph" transitive? In other words, suppose a graph G1 is an induced subgraph of a graph G2 and G2 is an induced subgraph of G3. Does it follow that G1 is an induced subgraph of G3?

Let G and G1 be two graphs. We say that the graph G is G1 -free if G1 is not an induced subgraph of G. So for example the Petersen graph is triangle-free because the triangle K3 is not an induced subgraph of the Petersen graph. The Petersen graph is also claw-free since the claw is not an induced subgraph of the Petersen graph.

Questions:
  1. Keeping in mind this problem from a past lesson outline a way to determine if a graph is triangle-free if you are given the adjacency matrix of the graph.
  2. Is the graph shown in figure 26.2 a claw-free graph?
    Is this a claw-free graph?
    Fig 26.2, Is this graph claw-free?

Answers


© C. Mawata