contraction of a graph

In mathematics, a graph contraction is a process where two adjacent vertices in a graph are merged into a single new vertex. This new vertex connects to all vertices that were originally connected to either of the merged vertices. This transformation results in a new graph, which is considered a contraction of the original.

A significant application of graph contraction is in determining if a graph is planar. A graph is planar if it can be drawn on a flat surface without any edges crossing. According to a theorem by K. Wagner, a graph is planar if and only if it cannot be contracted to form either the complete graph on five vertices (K₅) or the complete bipartite graph K_3,3.1