Contrações em um grafo

Definição

A operação inversa da inflação, que toma um subgrafo conexo \(F\) de \(G\) e o substitui por um vértice conectado aos vizinhos de \(F\) em \(G-F\), recebe o nome de contração. Se o subgrafo \(F\) consiste de apenas de dois vértices conectados por uma aresta, a operação será dita ainda contração de aresta.

Veja a figura a seguir, a contração da aresta $e=xy$ :

Pensar em contrações se mostra conveniente quando tentamos identificar de que grafo provém determinada inflação.