Count Edges in an Undirected Graph: Algorithm and Code

Every undirected edge appears twice in an adjacency list (once for each endpoint), so counting edges reduces to a single traversal and a divide-by-2.

That one-line insight is the Handshaking Lemma. It converts what looks like a graph enumeration problem into a straightforward sum-and-divide operation with no secondary loops.

Edge storage in undirected graphs

An adjacency list represents a graph as a collection of vertex-indexed lists, where each list holds the neighbours of that vertex.

For an undirected graph, edge (u, v) is symmetric: u is a neighbour of v and v is a neighbour of u. The adjacency list captures both facts as separate entries. Edge (0, 1) means vertex 0’s list contains 1 and vertex 1’s list contains 0. These are not two edges; they are two representations of the same edge.

This structural symmetry is similar to the problem of finding symmetric pairs in arrays, where a pair (a, b) and its mirror (b, a) represent one logical relationship stored at two positions. An undirected edge (u, v) works the same way: one edge, two adjacency list entries.

The consequence is direct: sum all adjacency list lengths and you get exactly 2 times the number of edges. Halve that total and you have the edge count.

The Handshaking Lemma

The degree of a vertex is the count of edges incident to it. For a vertex with adjacency list [1, 2, 3], degree is 3.

The Handshaking Lemma states that for any finite undirected graph, the sum of all vertex degrees equals twice the number of edges. The name comes from a classic observation: in a room where every handshake is an edge between two people, counting the total hands shaken across all participants counts every handshake twice (once for each person involved).

More precisely, each edge (u, v) contributes 1 to degree(u) and 1 to degree(v), a total contribution of 2. Summed over all edges, this gives:

degree_sum = 2 times the number of edges

Rearranged: the number of edges equals degree_sum divided by 2.

Since degree(v) equals the length of v’s adjacency list, the formula becomes:

number of edges = (sum of all adjacency list lengths) / 2

One useful property falls out of this: in any undirected graph with no self-loops, the degree sum is always even. An odd degree sum during graph construction is a reliable signal of a bug in the edge-insertion code.

Algorithm and worked example

Steps

• Step 1: Initialise degree_sum = 0.
• Step 2: For each vertex v, add the length of v’s adjacency list to degree_sum.
• Step 3: Return degree_sum // 2 (integer division).

No visited array. No marking. No sorting. Three lines of logic.

Worked example

Graph: 4 vertices (0, 1, 2, 3) and 4 edges: (0, 1), (0, 2), (1, 2), (1, 3).

Adjacency list:

• Vertex 0: [1, 2] (degree 2)
• Vertex 1: [0, 2, 3] (degree 3)
• Vertex 2: [0, 1] (degree 2)
• Vertex 3: [1] (degree 1)

Calculation:

• degree_sum = 2 + 3 + 2 + 1 = 8
• edge_count = 8 / 2 = 4

Verification: the explicit edges are (0, 1), (0, 2), (1, 2), (1, 3). That is 4 edges. Result matches.

Code implementation

Python

def count_edges(adj):
    """
    adj: dict mapping each vertex to a list of its neighbours.
    Returns the number of edges in the undirected graph.
    """
    degree_sum = 0
    for neighbors in adj.values():
        degree_sum += len(neighbors)
    return degree_sum // 2


# Example
adj = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1]
}
print(count_edges(adj))  # Output: 4

C++

#include <iostream>
#include <vector>
using namespace std;

int countEdges(vector<vector<int>>& adj) {
    int degreeSum = 0;
    for (const auto& neighbors : adj) {
        degreeSum += neighbors.size();
    }
    return degreeSum / 2;
}

int main() {
    // 4 vertices, edges: (0,1), (0,2), (1,2), (1,3)
    vector<vector<int>> adj = {
        {1, 2},
        {0, 2, 3},
        {0, 1},
        {1}
    };
    cout << countEdges(adj) << endl;  // Output: 4
    return 0;
}

Both implementations iterate once over each vertex header and once over each adjacency list entry. The Python version uses a dict; the C++ version uses a vector of vectors indexed by vertex number.

Complexity and edge cases

Metric	Value	Notes
Time	O(V + E)	One pass over V vertex headers; 2E adjacency entries total
Extra space	O(1)	Only a single integer counter; input adjacency list is not copied

The adjacency list input itself occupies O(V + E) memory (V list headers plus 2E list entries). This is the standard cost of the representation, not a cost added by the algorithm. For a detailed breakdown of how adjacency lists compare to adjacency matrices on space, see space complexity of algorithms with examples.

Disconnected graphs

The algorithm works unchanged on disconnected graphs. Vertices with no edges have empty adjacency lists (degree 0) and contribute nothing to degree_sum. The formula still produces the correct total edge count across all components.

Self-loops

A self-loop at vertex v is an edge from v back to v. Most adjacency list implementations represent this by adding v to its own neighbour list, which increases degree(v) by 2 (both endpoints are v). The Handshaking Lemma still holds: the self-loop contributes 2 to the degree sum, and dividing by 2 gives the correct edge count.

Adjacency matrix approach

If the input is an adjacency matrix, sum all entries in the upper triangle (the matrix is symmetric for undirected graphs). Time becomes O(V squared) since the entire matrix must be scanned. Adjacency lists are the better representation for sparse graphs where E is much smaller than V squared.

In placement assessments

Graph traversal problems appear in service-tier company coding rounds as warm-up questions. They test foundational understanding before BFS, DFS, connected components, and cycle detection. Edge counting is a typical starter: it is conceptually accessible but rewards candidates who know the Handshaking Lemma over those who attempt a brute-force O(V squared) double-loop approach.

The GeeksforGeeks walkthrough of this problem lists the same adjacency-list approach as canonical. That’s a useful signal about how widely this solution pattern appears in placement preparation resources.

Companies often use edge counting as a sub-problem inside larger questions: “Find the number of edges in each connected component” is a direct extension of BFS or DFS output combined with this formula. Knowing the degree-sum shortcut makes that extension a one-liner rather than a nested loop.

The O(V + E) traversal pattern from this problem recurs throughout graph algorithms. Internalising why it works (every edge contributes 2 to the adjacency list total) is more durable than memorising the formula as a fact, because the same reasoning applies when counting edges in weighted graphs, multigraphs, or subgraphs extracted from BFS trees.

Graph traversal is the foundation of interview-round DSA problems, from edge counting through BFS to shortest-path algorithms. The same adjacency-list logic appears in AI systems: knowledge graphs, retrieval-augmented generation pipelines, and tool-calling agents all traverse edge relationships at query time. TinkerLLM is where those experiments run against live LLM APIs; at ₹499, it costs less than most algorithm textbooks and covers the AI layer that degree syllabi rarely reach.