LeetCode 2508 - Add Edges to Make Degrees of All Nodes Even

The problem gives us an undirected graph with n nodes and a list of edges. Each edge connects two different nodes, and the graph may contain multiple disconnected components.

leetcodehardhash-tablegraph-theory

LeetCode Problem 2508

Difficulty: 🔴 Hard
Topics: Hash Table, Graph Theory

Solution

Problem Understanding

The problem gives us an undirected graph with n nodes and a list of edges. Each edge connects two different nodes, and the graph may contain multiple disconnected components.

Our task is to determine whether it is possible to add at most two new edges so that every node in the graph ends up having an even degree. A node's degree is simply the number of edges connected to it.

There are several important restrictions:

  • We cannot add self-loops, meaning we cannot connect a node to itself.
  • We cannot add duplicate edges, meaning if an edge already exists between two nodes, we cannot add it again.
  • We may add zero, one, or two edges.

The output is a boolean value:

  • Return true if it is possible to make all node degrees even.
  • Return false otherwise.

The constraints are large:

  • Up to 10^5 nodes
  • Up to 10^5 edges

This immediately tells us that any solution involving exhaustive graph modification or brute-force testing of all edge combinations will be too slow. We need an approach close to linear time.

A key graph theory property is that the number of nodes with odd degree in any undirected graph is always even. This fact is extremely important because it dramatically limits the possible cases we need to consider.

Important edge cases include:

  • The graph may already have all even degrees, in which case the answer is immediately true.
  • There may be exactly two odd-degree nodes.
  • There may be exactly four odd-degree nodes.
  • There may be more than four odd-degree nodes, which is impossible to fix with only two added edges.
  • Some required edges may already exist, preventing us from using an otherwise valid pairing.
  • The graph may be disconnected, but connectivity does not matter for degree parity.

Approaches

Brute Force Approach

A brute-force solution would try every possible set of up to two additional edges and check whether all node degrees become even afterward.

To do this, we could:

  1. Enumerate every possible edge (u, v) where u != v and the edge does not already exist.
  2. Try:
  • Adding no edges
  • Adding one edge
  • Adding every pair of possible edges
  1. After each attempt, recompute node degrees and verify whether all are even.

This approach is correct because it explicitly checks all valid possibilities. However, it is far too slow.

There are up to O(n^2) possible edges. Trying all pairs of edges would require O(n^4) combinations in the worst case, which is impossible for n = 10^5.

Optimal Observation

The critical observation comes from graph parity.

Adding one edge changes the parity of exactly two nodes because both endpoint degrees increase by one.

This means:

  • One added edge can fix exactly two odd-degree nodes.
  • Two added edges can fix at most four odd-degree nodes.

Therefore:

  • If the graph has more than four odd-degree nodes, the answer is immediately false.

  • We only need to handle cases where the number of odd-degree nodes is:

  • 0

  • 2

  • 4

This dramatically simplifies the problem.

We store the graph using adjacency sets so we can quickly determine whether an edge already exists.

Then we analyze the odd-degree nodes:

  • 0 odd nodes → already valid
  • 2 odd nodes → either connect them directly, or connect both through an intermediate node
  • 4 odd nodes → test all pairings

This leads to an efficient linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(n^2) Tries all possible added edge combinations
Optimal O(n + m) O(n + m) Uses odd-degree parity observations

Algorithm Walkthrough

Step 1: Build the Graph

Create:

  • A degree array to track node degrees
  • An adjacency set for each node to allow constant-time edge existence checks

For every edge (u, v):

  • Increment degree[u]
  • Increment degree[v]
  • Add each node to the other's adjacency set

We use sets because checking whether an edge already exists must be efficient.

Step 2: Collect Odd-Degree Nodes

Traverse all nodes from 1 to n.

If degree[node] % 2 == 1, add the node to the odd_nodes list.

Because of graph theory properties, the number of odd-degree nodes will always be even.

Step 3: Handle the Case of Zero Odd Nodes

If there are no odd-degree nodes, every node already has even degree.

Return true.

Step 4: Handle the Case of Two Odd Nodes

Suppose the odd nodes are a and b.

There are two possibilities:

  1. Direct connection
  2. Connection through an intermediate node

Direct Connection

If edge (a, b) does not already exist, we can add it.

Both degrees become even, so return true.

Intermediate Node

If (a, b) already exists, we cannot add it again.

Instead, try to find some node x such that:

  • (a, x) does not exist
  • (b, x) does not exist

Then we can add:

  • (a, x)
  • (b, x)

This flips parity for all three involved nodes:

  • a becomes even
  • b becomes even
  • x changes twice, so it remains even

If such a node exists, return true.

Otherwise return false.

Step 5: Handle the Case of Four Odd Nodes

Suppose the odd nodes are:

a, b, c, d

We can only use two edges, so we must pair them up.

There are exactly three possible pairings:

  1. (a, b) and (c, d)
  2. (a, c) and (b, d)
  3. (a, d) and (b, c)

For each pairing:

  • Check whether both edges do not already exist
  • If both are valid, return true

If none work, return false.

Step 6: Handle More Than Four Odd Nodes

If the graph has more than four odd-degree nodes, two edges are insufficient.

Return false.

Why it works

The algorithm works because each added edge flips the parity of exactly two nodes.

Therefore:

  • Two odd nodes can be fixed with one edge.
  • Four odd nodes can be fixed with two edges.
  • More than four odd nodes cannot possibly be fixed with only two edges.

The algorithm exhaustively checks all valid parity-fixing configurations while respecting the constraint that duplicate edges are forbidden.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        graph = defaultdict(set)
        degree = [0] * (n + 1)

        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            degree[u] += 1
            degree[v] += 1

        odd_nodes = []

        for node in range(1, n + 1):
            if degree[node] % 2 == 1:
                odd_nodes.append(node)

        if len(odd_nodes) == 0:
            return True

        if len(odd_nodes) == 2:
            a, b = odd_nodes

            if b not in graph[a]:
                return True

            for node in range(1, n + 1):
                if (
                    node != a
                    and node != b
                    and node not in graph[a]
                    and node not in graph[b]
                ):
                    return True

            return False

        if len(odd_nodes) == 4:
            a, b, c, d = odd_nodes

            pairings = [
                ((a, b), (c, d)),
                ((a, c), (b, d)),
                ((a, d), (b, c)),
            ]

            for (u1, v1), (u2, v2) in pairings:
                if v1 not in graph[u1] and v2 not in graph[u2]:
                    return True

            return False

        return False

The implementation begins by constructing an adjacency-set representation of the graph. This allows constant-time checks for whether an edge already exists, which is essential because duplicate edges are forbidden.

The degree array tracks the degree of every node while edges are processed. After building the graph, we collect all odd-degree nodes into odd_nodes.

The solution then branches based on the number of odd-degree nodes.

If there are zero odd nodes, the graph already satisfies the requirement.

If there are two odd nodes, the implementation first checks whether they can be connected directly. If not, it searches for an intermediate node that can connect to both odd nodes without violating edge constraints.

If there are four odd nodes, the implementation tests the three possible pairings.

Any case with more than four odd-degree nodes is immediately impossible.

Go Solution

package main

func isPossible(n int, edges [][]int) bool {
	graph := make([]map[int]bool, n+1)
	degree := make([]int, n+1)

	for i := 1; i <= n; i++ {
		graph[i] = make(map[int]bool)
	}

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u][v] = true
		graph[v][u] = true

		degree[u]++
		degree[v]++
	}

	oddNodes := []int{}

	for node := 1; node <= n; node++ {
		if degree[node]%2 == 1 {
			oddNodes = append(oddNodes, node)
		}
	}

	if len(oddNodes) == 0 {
		return true
	}

	if len(oddNodes) == 2 {
		a := oddNodes[0]
		b := oddNodes[1]

		if !graph[a][b] {
			return true
		}

		for node := 1; node <= n; node++ {
			if node != a &&
				node != b &&
				!graph[a][node] &&
				!graph[b][node] {
				return true
			}
		}

		return false
	}

	if len(oddNodes) == 4 {
		a := oddNodes[0]
		b := oddNodes[1]
		c := oddNodes[2]
		d := oddNodes[3]

		pairings := [][][]int{
			{{a, b}, {c, d}},
			{{a, c}, {b, d}},
			{{a, d}, {b, c}},
		}

		for _, pairing := range pairings {
			u1 := pairing[0][0]
			v1 := pairing[0][1]

			u2 := pairing[1][0]
			v2 := pairing[1][1]

			if !graph[u1][v1] && !graph[u2][v2] {
				return true
			}
		}

		return false
	}

	return false
}

The Go implementation follows the same logic as the Python solution. The primary difference is the graph representation.

Instead of Python sets, Go uses map[int]bool for adjacency checks. This provides efficient constant-time lookups for determining whether an edge already exists.

Slices are used to store odd-degree nodes and candidate pairings. Since all values fit comfortably within standard integer ranges, integer overflow is not a concern.

Worked Examples

Example 1

Input:

n = 5
edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]

Step 1: Compute Degrees

Node Degree
1 2
2 4
3 2
4 2
5 1

Wait carefully, node 5 has degree 1 and node 2 has degree 4.

Actually, node 5 is odd and no other node is odd, which violates the handshaking theorem. Recalculate:

Edges touching node 4:

  • (3,4)
  • (4,2)
  • (1,4)

Degree of node 4 is 3.

Updated table:

Node Degree
1 2
2 4
3 2
4 3
5 1

Odd nodes:

[4, 5]

Step 2: Try Direct Connection

Check whether edge (4,5) exists.

It does not.

Add edge (4,5).

Updated degrees:

Node New Degree
4 4
5 2

All degrees are now even.

Return true.

Example 2

Input:

n = 4
edges = [[1,2],[3,4]]

Step 1: Compute Degrees

Node Degree
1 1
2 1
3 1
4 1

Odd nodes:

[1, 2, 3, 4]

Step 2: Try Pairings

Possible pairings:

Pairing Valid?
(1,2) and (3,4) No, both already exist
(1,3) and (2,4) Yes
(1,4) and (2,3) Also yes

We can add:

(1,3)
(2,4)

All node degrees become even.

Return true.

Example 3

Input:

n = 4
edges = [[1,2],[1,3],[1,4]]

Step 1: Compute Degrees

Node Degree
1 3
2 1
3 1
4 1

Odd nodes:

[1, 2, 3, 4]

Step 2: Try Pairings

Pairing Valid?
(1,2) and (3,4) No, (1,2) exists
(1,3) and (2,4) No, (1,3) exists
(1,4) and (2,3) No, (1,4) exists

No valid pairing exists.

Return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Build graph and scan nodes once
Space O(n + m) Adjacency sets store all edges

The graph construction processes every edge exactly once, giving O(m) work. Scanning all nodes for odd degrees costs O(n).

The remaining logic handles at most four odd nodes, so those checks are constant time except for the intermediate-node search in the two-odd-node case, which scans all nodes once. Therefore, the total complexity remains linear.

The adjacency sets require O(m) storage, and the degree array requires O(n) space.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        graph = defaultdict(set)
        degree = [0] * (n + 1)

        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            degree[u] += 1
            degree[v] += 1

        odd_nodes = []

        for node in range(1, n + 1):
            if degree[node] % 2 == 1:
                odd_nodes.append(node)

        if len(odd_nodes) == 0:
            return True

        if len(odd_nodes) == 2:
            a, b = odd_nodes

            if b not in graph[a]:
                return True

            for node in range(1, n + 1):
                if (
                    node != a
                    and node != b
                    and node not in graph[a]
                    and node not in graph[b]
                ):
                    return True

            return False

        if len(odd_nodes) == 4:
            a, b, c, d = odd_nodes

            pairings = [
                ((a, b), (c, d)),
                ((a, c), (b, d)),
                ((a, d), (b, c)),
            ]

            for (u1, v1), (u2, v2) in pairings:
                if v1 not in graph[u1] and v2 not in graph[u2]:
                    return True

            return False

        return False

sol = Solution()

assert sol.isPossible(
    5,
    [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
) == True  # Provided example 1

assert sol.isPossible(
    4,
    [[1,2],[3,4]]
) == True  # Provided example 2

assert sol.isPossible(
    4,
    [[1,2],[1,3],[1,4]]
) == False  # Provided example 3

assert sol.isPossible(
    3,
    [[1,2],[2,3],[3,1]]
) == True  # Already all even

assert sol.isPossible(
    6,
    [[1,2],[2,3],[3,4],[4,5]]
) == True  # Two odd nodes connect directly

assert sol.isPossible(
    4,
    [[1,2],[2,3],[3,4],[4,1]]
) == True  # Cycle graph already valid

assert sol.isPossible(
    6,
    [[1,2],[1,3],[1,4],[1,5],[1,6]]
) == False  # More than four odd nodes

assert sol.isPossible(
    5,
    [[1,2],[2,3],[3,4],[4,1],[1,5]]
) == True  # Needs intermediate node

assert sol.isPossible(
    5,
    [[1,2],[1,3],[1,4],[1,5]]
) == True  # Four odd nodes with valid pairing
Test Why
Example 1 Verifies direct connection of two odd nodes
Example 2 Verifies four-node pairing logic
Example 3 Verifies impossible pairing case
Triangle graph Confirms already-even graph handling
Path graph Verifies simple direct edge addition
Cycle graph Confirms valid even-degree cycle
Star graph with 5 leaves Tests more-than-four odd nodes
Intermediate-node case Verifies indirect fixing logic
Four odd nodes valid pairing Confirms pairing enumeration

Edge Cases

Graph Already Has All Even Degrees

A common mistake is forgetting that adding zero edges is allowed. If every node already has even degree, the correct answer is immediately true.

The implementation handles this by checking:

if len(odd_nodes) == 0:
    return True

This avoids unnecessary processing and ensures correctness.

Two Odd Nodes Already Connected

Suppose the graph has exactly two odd-degree nodes, but they already share an edge. A naive implementation might incorrectly assume the graph is impossible.

However, we may still fix the graph by using an intermediate node.

For example:

a -- b

If there exists a node x with no edges to either a or b, we can add:

(a, x)
(b, x)

The implementation explicitly searches for such a node.

Four Odd Nodes With Blocked Pairings

Another subtle case occurs when four odd nodes exist, but some required pairing edges already exist.

Since duplicate edges are forbidden, not every pairing is valid.

The implementation carefully tests all three possible pairings and verifies that neither edge already exists before accepting the configuration.

This guarantees correctness even in dense graphs where many candidate edges are unavailable.