Editing Graph theory (section)

=== Subgraphs, induced subgraphs, and minors ===
A common problem, called the [[subgraph isomorphism problem]], is finding a fixed graph as a [[Glossary of graph theory#Subgraphs|subgraph]] in a given graph. One reason to be interested in such a question is that many [[graph properties]] are ''hereditary'' for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Finding maximal subgraphs of a certain kind is often an [[NP-complete problem]]. For example:
* Finding the largest complete subgraph is called the [[clique problem]] (NP-complete).

One special case of subgraph isomorphism is the [[graph isomorphism problem]]. It asks whether two graphs are isomorphic. It is not known whether this problem is NP-complete, nor whether it can be solved in polynomial time.

A similar problem is finding [[induced subgraph]]s in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example:
* Finding the largest edgeless induced subgraph or [[Independent set (graph theory)|independent set]] is called the [[independent set problem]] (NP-complete).

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A [[Minor (graph theory)|minor]] or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. For example, [[Wagner's theorem|Wagner's Theorem]] states: 
* A graph is [[planar graph|planar]] if it contains as a minor neither the [[complete bipartite graph]] ''K''<sub>3,3</sub> (see the [[Three-cottage problem]]) nor the complete graph ''K''<sub>5</sub>.

A similar problem, the subdivision containment problem, is to find a fixed graph as a [[Subdivision (graph theory)|subdivision]] of a given graph. A [[Subdivision (graph theory)|subdivision]] or [[Homeomorphism (graph theory)|homeomorphism]] of a graph is any graph obtained by subdividing some (or no) edges. Subdivision containment is related to graph properties such as [[Planarity (graph theory)|planarity]]. For example, [[Kuratowski's theorem|Kuratowski's Theorem]] states:
* A graph is [[Planar graph|planar]] if it contains as a subdivision neither the [[complete bipartite graph]] ''K''<sub>3,3</sub> nor the [[complete graph]] ''K''<sub>5</sub>.

Another problem in subdivision containment is the [[Kelmans–Seymour conjecture]]:
* Every [[K-vertex-connected graph|5-vertex-connected]] graph that is not [[Planar graph|planar]] contains a [[Homeomorphism (graph theory)|subdivision]] of the 5-vertex [[complete graph]] ''K''<sub>5</sub>.
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their ''point-deleted subgraphs''. For example:
* The [[reconstruction conjecture]]