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/

Definition:

Given a graph G, and a set of vertices W which is a subset of V, the vertex subset of G, the subgraph W' of G induced by the set W is the graph consisting of the set of vertices W and together with those edges of G that join vertices in W. (Sometimes one says that the subgraph W' is generated by the set of vertices W.)

1. For each of the graph shown below:

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

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

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.

G H L M N P Back to Geometric Structures page