Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Foundations > Subgraphs and Supergraphs
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Subgraphs and Supergraphs

A subgraph of a graph is a graph such that and .

would then be a supergraph for .

Example:
Subgraph and Supergraph

Figure 9: Subgraph and Supergraph

The cycle of length 6 (red vertices and edges) is a subgraph of the whole graph. Notice that not all edges connecting the shaded vertices belong to the subgraph. The subgraph is a supergraph for the cycle.



is an induced subgraph of if all edges of connecting vertices in belong to .

Example:
An Induced Subgraph

Figure 10: An Induced Subgraph

The six red vertices and seven red edges (a cycle with a chord) form an induced subgraph of the whole graph. All edges connecting the shaded vertices belong to the subgraph.



A subgraph containing all vertices of the graph is called spanning.

 
 
go backgo forward
go backgo forward