**Subgraphs**

A *subgraph* *S* of a graph *G* is a graph whose set of vertices and set of edges
are all subsets of *G*. (Since every set is a subset of itself, every graph is a subgraph of itself.)

All the edges and vertices of *G* might not be present in *S*; but if a vertex is present
in *S*, it has a corresponding vertex in *G* and any edge that connects two vertices in *S* will
also connect the corresponding vertices in *G*.
All of these graphs are subgraphs of the first graph.

A *vertex-induced subgraph* is one that consists of some of the vertices of the original
graph and all of the edges that connect them in the original. An *edge-induced subgraph*
consists of some of the edges of the original graph and the vertices that are at their endpoints.

The second two figures are vertex-induced subgraphs of the first figure. | |

The second two figures are edge-induced subgraphs of the first figure. |

The second figure is a subgraph of the first figure, but it is neither edge-induced nor vertex-induced. |

Copyright © 1999-2000 SciMathMN