**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