Add Edges to Make Degrees of All Nodes Even

Problem

There is an undirected graph consisting of n nodes numbered from 1 to n. You are given the integer n and a 2D array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi. The graph can be disconnected.

You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Return true if it is possible to make the degree of each node in the graph even, otherwise return false.

The degree of a node is the number of edges connected to it.

Examples

Example 1:

graph LR

    subgraph Original[" "]
        A1(1) --- B1(2) & D1(4)
        B1 --- D1 & C1(3) & E1(5)
        C1 --- D1
    end
    
    subgraph After[" "]
        A2(1) --- B2(2) & D2(4)
        B2 --- D2 & C2(3) & E2(5)
        C2 --- D2
        D2 --- E2
    end
    
    Original --> After
    
linkStyle 12 stroke:red,stroke-width:2px

1
2
3


Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output: true
Explanation: The above diagram shows a valid way of adding an edge. Every node in the resulting graph is connected to an even number of edges.

Example 2:

graph LR

    subgraph Original[" "]
        A1(1) --- B1(2)
        C1(3) --- D1(4)
    end
    
    subgraph After[" "]
        A2(1) --- B2(2) & C2(3)
        C2 --- D2(4)
        B2 --- D2
    end
    
    Original --> After
    
linkStyle 3 stroke:red,stroke-width:2px
linkStyle 5 stroke:red,stroke-width:2px

1
2
3


Input: n = 4, edges = [[1,2],[3,4]]
Output: true
Explanation: The above diagram shows a valid way of adding two edges.

Example 3:

graph TD;
A(1) --- B(2) & C(3) & D(4)

1
2
3


Input: n = 4, edges = [[1,2],[1,3],[1,4]]
Output: false
Explanation: It is not possible to obtain a valid graph with adding at most 2 edges.

Constraints:

3 <= n <= 10^5
2 <= edges.length <= 10^5
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
There are no repeated edges.

Solution

Method 1 – Degree Parity Analysis and Casework

Intuition

The key insight is that a graph can have all nodes with even degrees if and only if the number of nodes with odd degrees is even (by the Handshaking Lemma). Since we can add at most two edges, we can only fix up to four odd-degree nodes. We check all possible ways to connect these odd-degree nodes with at most two new edges, ensuring no self-loops or duplicate edges.

Approach

Count Degrees:

Compute the degree of each node.

Identify Odd-Degree Nodes:

Collect all nodes with odd degrees.

Case Analysis:

If there are 0 odd-degree nodes, return True.
If there are 2 odd-degree nodes, check if they can be connected directly or via a third node.
If there are 4 odd-degree nodes, check all pairings to connect them with two edges.
Otherwise, return False.

Edge Existence Check:

Use a set or map to quickly check if an edge already exists (to avoid duplicates).

Return Result:

Return True if a valid configuration is found, else False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class Solution {
public:
   bool isPossible(int n, vector<vector<int>>& edges) {
      vector<int> deg(n + 1, 0);
      unordered_set<long long> st;
      for (auto& e : edges) {
        deg[e[0]]++;
        deg[e[1]]++;
        long long key = min(e[0], e[1]) * 100000LL + max(e[0], e[1]);
        st.insert(key);
      }
      vector<int> odd;
      for (int i = 1; i <= n; ++i)
        if (deg[i] % 2) odd.push_back(i);
      if (odd.size() == 0) return true;
      if (odd.size() == 2) {
        int a = odd[0], b = odd[1];
        long long key = min(a, b) * 100000LL + max(a, b);
        if (!st.count(key)) return true;
        for (int i = 1; i <= n; ++i) {
           if (i == a || i == b) continue;
           long long k1 = min(a, i) * 100000LL + max(a, i);
           long long k2 = min(b, i) * 100000LL + max(b, i);
           if (!st.count(k1) && !st.count(k2)) return true;
        }
        return false;
      }
      if (odd.size() == 4) {
        vector<int> o = odd;
        for (int i = 0; i < 4; ++i) {
           for (int j = i + 1; j < 4; ++j) {
              vector<int> p = {0, 1, 2, 3};
              p.erase(p.begin() + j);
              p.erase(p.begin() + i);
              int a1 = o[i], b1 = o[j], a2 = o[p[0]], b2 = o[p[1]];
              long long k1 = min(a1, b1) * 100000LL + max(a1, b1);
              long long k2 = min(a2, b2) * 100000LL + max(a2, b2);
              if (!st.count(k1) && !st.count(k2)) return true;
           }
        }
        return false;
      }
      return false;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution {
   public boolean isPossible(int n, List<List<Integer>> edges) {
      int[] deg = new int[n + 1];
      Set<Long> st = new HashSet<>();
      for (List<Integer> e : edges) {
        deg[e.get(0)]++;
        deg[e.get(1)]++;
        long key = Math.min(e.get(0), e.get(1)) * 100000L + Math.max(e.get(0), e.get(1));
        st.add(key);
      }
      List<Integer> odd = new ArrayList<>();
      for (int i = 1; i <= n; ++i)
        if (deg[i] % 2 != 0) odd.add(i);
      if (odd.size() == 0) return true;
      if (odd.size() == 2) {
        int a = odd.get(0), b = odd.get(1);
        long key = Math.min(a, b) * 100000L + Math.max(a, b);
        if (!st.contains(key)) return true;
        for (int i = 1; i <= n; ++i) {
           if (i == a || i == b) continue;
           long k1 = Math.min(a, i) * 100000L + Math.max(a, i);
           long k2 = Math.min(b, i) * 100000L + Math.max(b, i);
           if (!st.contains(k1) && !st.contains(k2)) return true;
        }
        return false;
      }
      if (odd.size() == 4) {
        int[] o = new int[4];
        for (int i = 0; i < 4; ++i) o[i] = odd.get(i);
        for (int i = 0; i < 4; ++i) {
           for (int j = i + 1; j < 4; ++j) {
              int[] p = {0, 1, 2, 3};
              int a1 = o[i], b1 = o[j];
              int a2 = o[p[0] == i || p[0] == j ? p[2] : p[0]], b2 = o[p[1] == i || p[1] == j ? p[3] : p[1]];
              long k1 = Math.min(a1, b1) * 100000L + Math.max(a1, b1);
              long k2 = Math.min(a2, b2) * 100000L + Math.max(a2, b2);
              if (!st.contains(k1) && !st.contains(k2)) return true;
           }
        }
        return false;
      }
      return false;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution:
   def isPossible(self, n: int, edges: list[list[int]]) -> bool:
      deg = [0] * (n + 1)
      st = set()
      for a, b in edges:
        deg[a] += 1
        deg[b] += 1
        st.add((min(a, b), max(a, b)))
      odd = [i for i in range(1, n + 1) if deg[i] % 2]
      if len(odd) == 0:
        return True
      if len(odd) == 2:
        a, b = odd
        if (min(a, b), max(a, b)) not in st:
           return True
        for i in range(1, n + 1):
           if i == a or i == b:
              continue
           if (min(a, i), max(a, i)) not in st and (min(b, i), max(b, i)) not in st:
              return True
        return False
      if len(odd) == 4:
        o = odd
        from itertools import combinations
        for x, y in combinations(range(4), 2):
           rem = [i for i in range(4) if i != x and i != y]
           a1, b1 = o[x], o[y]
           a2, b2 = o[rem[0]], o[rem[1]]
           if (min(a1, b1), max(a1, b1)) not in st and (min(a2, b2), max(a2, b2)) not in st:
              return True
        return False
      return False

Complexity

⏰ Time complexity: O(n + m) where n is the number of nodes and m is the number of edges.
🧺 Space complexity: O(n + m) for degree array and edge set.

Problem#

Examples#

Solution#

Method 1 – Degree Parity Analysis and Casework#

Intuition#

Approach#

Code#

Complexity#