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