Watch 10 video solutions for Add Edges to Make Degrees of All Nodes Even, a hard level problem involving Hash Table, Graph. This walkthrough by codingMohan has 900 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
Input: n = 4, edges = [[1,2],[3,4]] Output: true Explanation: The above diagram shows a valid way of adding two edges.
Example 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 <= 1052 <= edges.length <= 105edges[i].length == 21 <= ai, bi <= nai != biProblem Overview: You are given an undirected graph with n nodes and a list of edges. The task is to determine whether you can add at most two new edges so that every node ends up with an even degree. Multiple edges between the same pair and self-loops are not allowed.
The key observation from graph theory: a graph has all even degrees only when the number of odd-degree vertices is zero. Adding one edge flips the parity (odd/even) of exactly two vertices. This means only a few configurations of odd-degree nodes are fixable with at most two added edges.
Approach 1: Divide and Conquer Approach (O(n + m))
Start by building a graph representation using adjacency sets from the edge list. Track the degree of every node and collect all nodes with odd degree. Because each added edge changes the parity of two nodes, there are only three possible cases to check: 0 odd nodes, 2 odd nodes, or 4 odd nodes.
If there are zero odd nodes, the graph already satisfies the condition. If there are two odd nodes a and b, try directly connecting them. If an edge already exists, search for an intermediate node x such that neither (a,x) nor (b,x) exists. If four odd nodes exist, try pairing them in the three possible combinations and verify that the required edges do not already exist. Using adjacency sets allows constant-time edge existence checks. Building the graph takes O(n + m) time and the pairing checks are constant, so the overall complexity remains O(n + m) with O(n + m) space.
Approach 2: Iterative Approach Using Stack (O(n + m))
An iterative traversal can be used to compute node degrees and validate graph structure. Push nodes onto a stack and process their adjacency lists to count incident edges. This traversal ensures every vertex and edge is visited once, giving a complete degree map.
After computing degrees, push odd-degree nodes into a container and apply the same parity rules: only 0, 2, or 4 odd vertices can potentially be fixed. Use the adjacency HashSet to test candidate edges while iterating through possible pairings. The stack-based traversal avoids recursion and works well when the graph is large or when recursion limits are a concern. Time complexity is O(n + m) and space complexity is also O(n + m) due to adjacency storage and the stack.
Both approaches rely on efficient edge existence checks using a hash table structure and standard graph degree properties. Understanding the parity behavior of vertices drastically reduces the search space from exponential possibilities to a few constant checks.
Recommended for interviews: The divide-and-conquer style parity analysis is what interviewers typically expect. It shows you recognize the odd-degree constraint and can reduce the problem to checking a few valid pairings. A brute-force mindset (trying many edges) shows understanding, but recognizing the parity rule and validating with hash lookups demonstrates strong graph reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer Degree Analysis | O(n + m) | O(n + m) | Best general solution. Quickly checks odd-degree configurations using adjacency hash sets. |
| Iterative Approach Using Stack | O(n + m) | O(n + m) | Useful when performing explicit graph traversal or avoiding recursion while computing node degrees. |