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.
family | obstruction |
bipartite graph | cycle graph for , 5, ... |
unit-distance graph on vertices | 74 minimal graphs |