Edge contraction

Edge contraction merges the endpoints of an edge into a single vertex and removes the contracted edge. The operation combines their incident edges, with loops and parallel edges handled according to the graph setting.

Graph minor: A graph obtained by deleting vertices or edges and contracting edges. Repeated edge contractions, together with deletions, produce graph minors.
Graph (discrete mathematics): A structure consisting of vertices connected by edges. Edge contraction is defined by transforming a graph's vertices and edges.
Karger’s algorithm: A randomized algorithm for finding a graph's minimum cut by repeatedly contracting random edges. It uses edge contraction as its central step while preserving a target cut with some probability.
Edge deletion: An operation that removes an edge while leaving its endpoints in the graph. Deletion removes an edge without identifying its endpoints.
Vertex identification: An operation that treats two or more vertices as a single vertex. Contracting an edge identifies precisely its two endpoints.
Incidence (graph theory): The relation in which an edge has a vertex as one of its endpoints. Contraction changes incidences by attaching endpoint edges to the merged vertex.
Treewidth: A graph parameter measuring how closely a graph resembles a tree. Contraction preserves the upper bound on treewidth, making it useful in structural arguments.
Vertex deletion: An operation that removes a vertex and all edges incident to it. Unlike contraction, vertex deletion discards an endpoint rather than merging it.
Loop (graph theory): An edge whose two ends are incident with the same vertex. Other edges between the contracted endpoints can become loops after identification.
Degree (graph theory): The number of edges incident to a vertex, with conventions depending on graph type. The merged vertex's degree depends on the endpoint degrees and shared incident edges.

Linked from 7 pages