Red Arrow Documentation
Basics
Graph
Graph Fusion

Graph Fusion

  • Let u and v be two distinct vertices in graph G.
  • The fusion of the vertices u and v are treated as a single new vertex w and every edge which was incident on u and v, are now incident on w.
  • After fusion, number of vertices in the graph always decreases by one.
    • If original graph has n vertices, after fusion it will have n-1 vertices.
  • But, the number of edges may increase or decrease or remain the same.

In all the below diagrams, we fuse vertices B and C.

=> Simple graph:

fusion 1

=> Vertices reduced but edges remain same:

fusion 2

=> Fusion creating self-loop:

fusion 3

=> Fusion in graph with self-loop:

fusion 4

Credits: GeeksforGeeks