Forbidden graph characterization

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a branch of mathematics, many important families of <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a> can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> or <a href="/facts/Graph_minor/qn5eI22T">minor</a>.
A prototypical example of this phenomenon is <a href="/facts/Kuratowski%2527s_theorem/Enph2grQ">Kuratowski's theorem</a>, which states that a graph is <a href="/facts/Planar_graph/plREagr9">planar</a> (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K5 and the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> K3,3. For Kuratowski's theorem, the notion of containment is that of <a href="/facts/Graph_homeomorphism/WbFo1mNW">graph homeomorphism</a>, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs).

Forbidden graph characterization open-in-new

Forbidden graph characterization