# Add Edges to Make Degrees of All Nodes Even
**Difficulty:** HARD
[External](https://leetcode.com/problems/add-edges-to-make-degrees-of-all-nodes-even)
Canonical: https://scaleengineer.com/dsa/problems/add-edges-to-make-degrees-of-all-nodes-even
**Data structures:** Hash Table, Graph
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/add-edges-to-make-degrees-of-all-nodes-even/image0.png) 

**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:**

![](https://assets.glich.co/dsa/add-edges-to-make-degrees-of-all-nodes-even/image1.png) 

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

**Example 3:**

![](https://assets.glich.co/dsa/add-edges-to-make-degrees-of-all-nodes-even/image2.png) 

**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 <= 105`
* `2 <= edges.length <= 105`
* `edges[i].length == 2`
* `1 <= ai, bi <= n`
* `ai != bi`
* There are no repeated edges.

# Approaches
## Case Analysis with Linear Scan for Helper Node
This approach categorizes the problem based on the number of nodes with odd degrees. The core idea is that to make a node's degree even, we must connect it to another node, which also changes the parity of the other node's degree. Thus, we must pair up odd-degree nodes. The number of odd-degree nodes must be even. Given we can add at most two edges, we can only solve the problem if there are 0, 2, or 4 odd-degree nodes. For the tricky case of 2 odd-degree nodes that are already connected, this method performs a simple linear scan to find a third 'helper' node.
**Time:** O(N + E), where N is the number of nodes and E is the number of edges. Graph construction takes O(N + E). Finding odd nodes takes O(N). The case for 2 odd nodes involves a linear scan of O(N), leading to a total complexity of O(N + E). · **Space:** O(N + E) to store the graph's adjacency sets.
**Pros:** The logic is straightforward and directly follows from the problem's constraints.; It correctly handles all cases based on the number of odd-degree nodes.
**Cons:** The linear scan for a helper node in the `m=2` case can be inefficient, with a complexity of O(N). For large N, this might result in a 'Time Limit Exceeded' error.
### Explanation
The fundamental observation is that adding an edge between two nodes flips the parity of their degrees. To make all degrees even, we must eliminate all nodes with odd degrees. This can only be done by adding edges between pairs of odd-degree nodes. The number of nodes with odd degrees in any graph is always even. Since we can add at most two edges, we can fix at most four odd-degree nodes.

The algorithm proceeds as follows:
1.  First, we compute the degree of every node and build an adjacency set representation of the graph for quick edge lookups.
2.  We identify all nodes with an odd degree and store them in a list.
3.  We analyze the number of odd-degree nodes (`m`):
    *   If `m = 0`, all degrees are even. We need 0 edges. Return `true`.
    *   If `m = 2`, let the nodes be `u` and `v`. We can add one edge `(u, v)` if it doesn't already exist. If it does exist, we must use two edges. We look for a 'helper' node `w` (different from `u` and `v`) and add edges `(u, w)` and `(v, w)`. This makes `deg(u)` and `deg(v)` even, while `deg(w)` is incremented twice, keeping its parity unchanged. We find `w` by iterating through all nodes from 1 to `n` and checking if `w` is not connected to `u` or `v`.
    *   If `m = 4`, let the nodes be `a, b, c, d`. We must use two edges. There are three ways to pair them up: `(a, b)` & `(c, d)`; `(a, c)` & `(b, d)`; `(a, d)` & `(b, c)`. We check if any of these three pairings consist of two non-existent edges. If so, we can add them and return `true`.
    *   If `m` is odd or greater than 4, it's impossible to solve. Return `false`.

Here is the Java implementation:
```java
class Solution {
    public boolean isPossible(int n, java.util.List<java.util.List<Integer>> edges) {
        java.util.Set<Integer>[] adj = new java.util.HashSet[n + 1];
        int[] degree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new java.util.HashSet<>();
        }

        for (java.util.List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            adj[u].add(v);
            adj[v].add(u);
            degree[u]++;
            degree[v]++;
        }

        java.util.List<Integer> oddNodes = new java.util.ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 != 0) {
                oddNodes.add(i);
            }
        }

        int m = oddNodes.size();
        if (m == 0) {
            return true;
        }
        if (m == 2) {
            int u = oddNodes.get(0);
            int v = oddNodes.get(1);
            if (!adj[u].contains(v)) {
                return true; // Add edge (u, v)
            } else {
                // Linearly scan for a helper node w
                for (int w = 1; w <= n; w++) {
                    if (w != u && w != v) {
                        if (!adj[u].contains(w) && !adj[v].contains(w)) {
                            return true; // Add edges (u, w) and (v, w)
                        }
                    }
                }
                return false;
            }
        }
        if (m == 4) {
            int a = oddNodes.get(0);
            int b = oddNodes.get(1);
            int c = oddNodes.get(2);
            int d = oddNodes.get(3);
            if (!adj[a].contains(b) && !adj[c].contains(d)) return true;
            if (!adj[a].contains(c) && !adj[b].contains(d)) return true;
            if (!adj[a].contains(d) && !adj[b].contains(c)) return true;
            return false;
        }
        
        return false;
    }
}
```
### Algorithm
- Build an adjacency set and calculate degrees for all nodes in `O(N + E)`.
- Identify all nodes with odd degrees and collect them in a list, `oddNodes`. This takes `O(N)`.
- If `oddNodes.size() == 0`, return `true`.
- If `oddNodes.size() == 2` (nodes `u`, `v`):
  - If edge `(u, v)` does not exist, return `true`.
  - Otherwise, iterate through all nodes `w` from 1 to `N`. If `w` is not `u` or `v`, and edges `(u, w)` and `(v, w)` do not exist, return `true`.
  - If no such `w` is found, return `false`.
- If `oddNodes.size() == 4` (nodes `a`, `b`, `c`, `d`):
  - Check the three possible pairings. If a valid pairing with non-existent edges is found, return `true`.
  - Otherwise, return `false`.
- For any other size of `oddNodes`, return `false`.

## Case Analysis with Optimized Helper Node Search
This approach refines the previous method by optimizing the most time-consuming part: finding a helper node. It uses the same case-based analysis on the number of odd-degree nodes (0, 2, or 4). However, for the case of 2 odd-degree nodes `u` and `v` that are already connected, it avoids a linear scan. Instead, it uses a set-based counting argument to determine in `O(min(degree(u), degree(v)))` time if a suitable helper node `w` exists, making the solution significantly faster in dense graphs or graphs with high-degree nodes.
**Time:** O(N + E). The graph construction and initial processing take O(N + E). The optimized check for the `m=2` case takes `O(min(degree(u), degree(v)))`, which is bounded by O(N) in the worst case but is very efficient on average and for sparse graphs. The overall complexity remains O(N + E). · **Space:** O(N + E) to store the graph's adjacency sets.
**Pros:** Highly efficient, avoiding the O(N) linear scan.; Passes even with large inputs and tight time constraints.; The logic is robust and covers all scenarios optimally.
**Cons:** The implementation of the optimized check is slightly more complex due to the set intersection and union size calculation.
### Explanation
This method builds upon the same logic as the first approach but introduces a crucial optimization. The setup (calculating degrees, building adjacency sets, finding odd-degree nodes) and the logic for 0 and 4 odd-degree nodes remain identical.

The improvement lies in handling the case where there are 2 odd-degree nodes, `u` and `v`, and the edge `(u, v)` already exists. Instead of iterating through all `n` nodes to find a helper `w`, we can determine its existence mathematically.

A helper node `w` must not be `u` or `v`, and it must not be a neighbor of `u` or `v`. This means `w` cannot be in the set `{u, v} U adj[u] U adj[v]`. A valid `w` exists if and only if this set of 'forbidden' nodes does not cover all `n` nodes in the graph.

The size of this forbidden set is `|{u, v} U adj[u] U adj[v]|`. Since `(u,v)` is an edge, `u` is in `adj[v]` and `v` is in `adj[u]`, so `{u,v}` is a subset of `adj[u] U adj[v]`. The size of the forbidden set is simply `|adj[u] U adj[v]|`.

Using the Principle of Inclusion-Exclusion, we have:
`|adj[u] U adj[v]| = |adj[u]| + |adj[v]| - |adj[u] intersect adj[v]|`

We can calculate the size of the intersection by iterating through the neighbors of the node with the smaller degree and checking for membership in the other's adjacency set. This takes `O(min(degree(u), degree(v)))` time.

If `n > |adj[u] U adj[v]|`, it means there is at least one node not in the forbidden set, so a helper `w` exists. We can return `true`. Otherwise, no such `w` exists, and we return `false`.

Here is the Java implementation for the optimized check:
```java
class Solution {
    public boolean isPossible(int n, java.util.List<java.util.List<Integer>> edges) {
        java.util.Set<Integer>[] adj = new java.util.HashSet[n + 1];
        int[] degree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new java.util.HashSet<>();
        }

        for (java.util.List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            adj[u].add(v);
            adj[v].add(u);
            degree[u]++;
            degree[v]++;
        }

        java.util.List<Integer> oddNodes = new java.util.ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 != 0) {
                oddNodes.add(i);
            }
        }

        int m = oddNodes.size();
        if (m == 0) {
            return true;
        }
        if (m == 2) {
            int u = oddNodes.get(0);
            int v = oddNodes.get(1);
            if (!adj[u].contains(v)) {
                return true;
            } else {
                // Optimized check for a helper node w
                int intersectionSize = 0;
                java.util.Set<Integer> s1 = adj[u];
                java.util.Set<Integer> s2 = adj[v];
                if (s1.size() > s2.size()) { // Iterate over smaller set
                    java.util.Set<Integer> temp = s1; s1 = s2; s2 = temp;
                }
                for (int neighbor : s1) {
                    if (s2.contains(neighbor)) {
                        intersectionSize++;
                    }
                }
                
                if (n > degree[u] + degree[v] - intersectionSize) {
                    return true;
                }
                return false;
            }
        }
        if (m == 4) {
            int a = oddNodes.get(0);
            int b = oddNodes.get(1);
            int c = oddNodes.get(2);
            int d = oddNodes.get(3);
            if (!adj[a].contains(b) && !adj[c].contains(d)) return true;
            if (!adj[a].contains(c) && !adj[b].contains(d)) return true;
            if (!adj[a].contains(d) && !adj[b].contains(c)) return true;
            return false;
        }
        
        return false;
    }
}
```
### Algorithm
- Build an adjacency set and calculate degrees for all nodes in `O(N + E)`.
- Identify all nodes with odd degrees and collect them in a list, `oddNodes`. This takes `O(N)`.
- If `oddNodes.size() == 0`, return `true`.
- If `oddNodes.size() == 2` (nodes `u`, `v`):
  - If edge `(u, v)` does not exist, return `true`.
  - Otherwise, calculate the size of the intersection of `adj[u]` and `adj[v]` in `O(min(degree(u), degree(v)))` time.
  - Use the inclusion-exclusion principle to find the size of `adj[u] U adj[v]`.
  - If `n > |adj[u] U adj[v]|`, a helper node exists, so return `true`. Otherwise, return `false`.
- If `oddNodes.size() == 4`, check the three possible pairings as in the previous approach.
- For any other size of `oddNodes`, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPossible(int n, List<List<Integer>> edges) {
    Set<Integer>[] g = new Set[n + 1];
    Arrays.setAll(g, k->new HashSet<>());
    for (var e : edges) {
      int a = e.get(0), b = e.get(1);
      g[a].add(b);
      g[b].add(a);
    }
    List<Integer> vs = new ArrayList<>();
    for (int i = 1; i <= n; ++i) {
      if (g[i].size() % 2 == 1) {
        vs.add(i);
      }
    }
    if (vs.size() == 0) {
      return true;
    }
    if (vs.size() == 2) {
      int a = vs.get(0), b = vs.get(1);
      if (!g[a].contains(b)) {
        return true;
      }
      for (int c = 1; c <= n; ++c) {
        if (a != c && b != c && !g[a].contains(c) && !g[c].contains(b)) {
          return true;
        }
      }
      return false;
    }
    if (vs.size() == 4) {
      int a = vs.get(0), b = vs.get(1), c = vs.get(2), d = vs.get(3);
      if (!g[a].contains(b) && !g[c].contains(d)) {
        return true;
      }
      if (!g[a].contains(c) && !g[b].contains(d)) {
        return true;
      }
      if (!g[a].contains(d) && !g[b].contains(c)) {
        return true;
      }
      return false;
    }
    return false;
  }
}

```

### Python

```python
class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool: g = defaultdict(set) for a, b in edges: g[a]. add(b) g[b]. add(a) vs = [i for i, v in g . items() if len(v) & 1] if len(vs) == 0: return True if len(vs) == 2: a, b = vs if a not in g[b]: return True return any(a not in g[c] and c not in g[b] for c in range(1, n + 1)) if len(vs) == 4: a, b, c, d = vs if a not in g[b] and c not in g[d]: return True if a not in g[c] and b not in g[d]: return True if a not in g[d] and b not in g[c]: return True return False return False

```

### CPP

```cpp
class Solution {
public:
  bool isPossible(int n, vector<vector<int>> &edges) {
    vector<unordered_set<int>> g(n + 1);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].insert(b);
      g[b].insert(a);
    }
    vector<int> vs;
    for (int i = 1; i <= n; ++i) {
      if (g[i].size() % 2) {
        vs.emplace_back(i);
      }
    }
    if (vs.size() == 0) {
      return true;
    }
    if (vs.size() == 2) {
      int a = vs[0], b = vs[1];
      if (!g[a].count(b))
        return true;
      for (int c = 1; c <= n; ++c) {
        if (a != b && b != c && !g[a].count(c) && !g[c].count(b)) {
          return true;
        }
      }
      return false;
    }
    if (vs.size() == 4) {
      int a = vs[0], b = vs[1], c = vs[2], d = vs[3];
      if (!g[a].count(b) && !g[c].count(d))
        return true;
      if (!g[a].count(c) && !g[b].count(d))
        return true;
      if (!g[a].count(d) && !g[b].count(c))
        return true;
      return false;
    }
    return false;
  }
};

```