Forbidden Subgraph

A graph is a forbidden subgraph if its presence as a subgraph of a given graph means it is not a member of some family of graphs. For example, a bipartite graph is a graph that does not contain an odd cycle as a subgraph.

More generally, there may be a family of (minimal) subgraphs whose presence characterizes if a given graph has some property. For example, a graph on 9 or fewer vertices is a unit-distance graph iff it does not contain one of a set of 74 minimal graphs as a subgraph. The following table summarizes some graph families which have forbidden subgraph obstructions.

bipartite graphcycle graph C_n for n=3, 5, ...
unit-distance graph on <9 vertices74 minimal graphs

See also

Forbidden Induced Subgraph, Forbidden Minor, Subgraph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Forbidden Subgraph." From MathWorld--A Wolfram Web Resource.

Subject classifications