Geometric Structures: Induced Subgraphs

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

Somewhat unexpectedly, the following idea turns out to be important not only in generating subgraphs from a given graph, but also for finding conditions that a family of graphs obey a particular property.

Definition:

Given a graph G, and a set of vertices W which is a subset of V, the vertex set of G, the subgraph W' of G induced by the set W is the graph consisting of the set of vertices W, where two vertices in W are joined when they are already joined in G. (Sometimes one says that the subgraph W' is generated by the set of vertices W.)

Example:

For the set of vertices W = {1, 4, 3} the induced subgraph is:

Note that though we started with a labeled graph the induced subgraph is treated as an unlabeled object.

For the set W = {1, 2, 4, 3} the induced subgraph would be:

1. For each of the graph shown below:

a. Find the subgraph induced by the set W = {0, 1, 2, 3 }

b. Is the cycle of length 4 an induced subgraph? (If so, what set W of vertices does the job?) (What is required is finding a set of vertices W in the graph such that W induces a cycle of length 4.)

c. Is the complete graph on 4 vertices an induced subgraph? (If so, what set W of vertices does the job?)

d. Is the path of length 4 an induced subgraph of? (If so, what set W of vertices does the job?)

e. Find all the different (e.g. non-isomorphic) graphs which are induced by sets W with 3 elements.

f. Find the longest length path induced in each graph.

g. Find the longest length cycle induced in each graph.


i. Is graph G planar?

j. Can you find a plane drawing of graph L?


G     

H

L

M


N

P