Counteredges

Counteredges are a concept used in graph theory to denote the reverse or opposite edge of a directed edge. Given a directed edge (u, v) in a graph, the counteredge is the edge (v, u). In many graph representations, especially bidirected or oriented graphs, edges may occur in counteredge pairs, signifying a two-way relationship between the same pair of vertices.

In formal terms, a directed graph can be viewed as a set of arcs, and for each arc (u, v) there exists the potential to consider its counteredge (v, u). When both arcs are present, the two vertices are mutually connected, forming a 2-cycle. When only one arc exists, the counteredge is absent, indicating a one-way relationship. In the context of converting between directed and undirected representations, an undirected edge {u, v} can be represented by a pair of counteredges (u, v) and (v, u) in a corresponding directed graph.

Counteredges also play a central role in network flow and residual graph concepts. In a flow network, an arc may carry flow in one direction and a counteredge (the reverse arc) in the opposite direction represents available residual capacity to reduce the current flow. This use is common in algorithms like Ford–Fulkerson, where counteredges enable adjustments to find augmenting paths.

Terminology varies across literature; some authors simply call the reverse edge the opposite edge or the reverse arc rather than a counteredge. Regardless of naming, the idea helps model reversible relationships, bidirectional communication, and the interplay between directed and undirected representations in graphs.