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
