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.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, edges = [[1,2],[2,3],[3,4]]

› Output: false

💡 Note: Current degrees: node 1=1, node 2=2, node 3=2, node 4=1, node 5=0. Nodes 1, 4, and 5 have odd degrees (3 total). Since we can add at most 2 edges affecting 4 endpoints, we cannot make all 3 odd-degree nodes even.

Example 2 — Already Valid

$ Input: n = 4, edges = [[1,2],[3,4]]

› Output: true

💡 Note: All nodes have degree 1 (odd). We have 4 odd nodes, so we can add edges (1,3) and (2,4) to make all degrees even.

Example 3 — Impossible Case

$ Input: n = 4, edges = [[1,2],[1,3],[1,4]]

› Output: false

💡 Note: Node 1 has degree 3, nodes 2,3,4 have degree 1. That's 4 odd nodes, but all pairs involve node 1, making it impossible with only 2 edges.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ edges.length ≤ 10⁵
edges[i].length == 2
1 ≤ a_i, b_i ≤ n
a_i ≠ b_i
There are no repeated edges

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is using the Handshaking Lemma: in any graph, the number of odd-degree vertices is always even. With at most 2 edge additions, we can only handle 0, 2, or 4 odd-degree nodes. Best approach uses mathematical analysis in O(n + m) time, O(n + m) space.

Common Approaches

✓ Brute Force - Try All Possible Edge Additions

⏱️ Time: O(n³) Space: O(n)

First calculate the degree of each node. Identify nodes with odd degrees. Then systematically try adding no edges, one edge, or two edges between all possible node pairs to see if we can make all degrees even.

Mathematical Graph Theory Approach

⏱️ Time: O(n + m) Space: O(n + m)

Apply Handshaking Lemma - in any graph, the number of vertices with odd degree is always even. Based on this count, determine if we can make all degrees even with at most 2 edge additions.

Brute Force - Try All Possible Edge Additions — Algorithm Steps

Step 1: Build degree array counting edges for each node
Step 2: Identify all nodes with odd degrees
Step 3: Try all combinations of adding 0, 1, or 2 edges
Step 4: Check if any combination makes all degrees even

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Degrees

Count edges for each node

Find Odd Nodes

Identify nodes with odd degrees

Try Additions

Test all possible edge combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_EDGES 1000

bool solution(int n, int edges[][2], int edgeCount) {
    // Calculate degrees
    int degree[n + 1];
    for (int i = 0; i <= n; i++) degree[i] = 0;
    
    // Store existing edges as strings
    char existingEdges[MAX_EDGES][20];
    int existingCount = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        degree[a]++;
        degree[b]++;
        sprintf(existingEdges[existingCount++], "%d,%d", a < b ? a : b, a < b ? b : a);
    }
    
    // Find odd degree nodes
    int oddNodes[n + 1];
    int oddCount = 0;
    
    for (int i = 1; i <= n; i++) {
        if (degree[i] % 2 == 1) {
            oddNodes[oddCount++] = i;
        }
    }
    
    // Case 1: Already all even
    if (oddCount == 0) {
        return true;
    }
    
    // Case 2: Try adding one edge
    if (oddCount == 2) {
        int a = oddNodes[0], b = oddNodes[1];
        char key[20];
        sprintf(key, "%d,%d", a < b ? a : b, a < b ? b : a);
        
        bool found = false;
        for (int i = 0; i < existingCount; i++) {
            if (strcmp(existingEdges[i], key) == 0) {
                found = true;
                break;
            }
        }
        
        if (a != b && !found) {
            return true;
        }
    }
    
    // Case 3: Try adding two edges
    if (oddCount == 4) {
        int pairs[3][2][2] = {
            {{oddNodes[0], oddNodes[1]}, {oddNodes[2], oddNodes[3]}},
            {{oddNodes[0], oddNodes[2]}, {oddNodes[1], oddNodes[3]}},
            {{oddNodes[0], oddNodes[3]}, {oddNodes[1], oddNodes[2]}}
        };
        
        for (int p = 0; p < 3; p++) {
            bool valid = true;
            for (int i = 0; i < 2; i++) {
                int a = pairs[p][i][0], b = pairs[p][i][1];
                char key[20];
                sprintf(key, "%d,%d", a < b ? a : b, a < b ? b : a);
                
                bool found = false;
                for (int j = 0; j < existingCount; j++) {
                    if (strcmp(existingEdges[j], key) == 0) {
                        found = true;
                        break;
                    }
                }
                
                if (a == b || found) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[MAX_EDGES][2];
    int edgeCount = 0;
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing of [[a,b],[c,d]...]
    char *ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            edges[edgeCount][1] = atoi(ptr);
            edgeCount++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
        }
        ptr++;
    }
    
    bool result = solution(n, edges, edgeCount);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to try all possible pairs of nodes for edge additions

✓ Linear Growth

Space Complexity

O(n)

Array to store degree of each node

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Add Edges to Make Degrees of All Nodes Even - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possible Edge Additions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler