A SUBGRAPH of a graph is another graph where every vertex and every edge that appear in the second graph appear in the first graph.

Mathematically, we say that a graph G' is a subgraph of G if every edge in E' is also in E, and every vertex in V' is also in V. Note that there does not necessarily need to be a path between all the vertices in a subgraph.

In the example below, graph G' is a subgraph of G since every edge in E' is in E, and every vertex in V' is in V. Note that it is not necessary to have a path between all the vertices in a subgraph.

The original graph G

Some subgraphs of G, G'

Choose topics to learn more about graph and graph algorithms

Back to AlgoNet Home