Determine whether you can add at most two new edges to an undirected graph so that every node ends up with even degree.
Add Edges To Make Degrees Of All Nodes Even
You are given an undirected graph with nodes labeled from $1n$ and a list of existing edges. You may add at most two new edges between pairs of distinct nodes that are not already directly connected.
Your task is to decide whether it is possible to make the degree of every node even after adding zero, one, or two edges.
A node's degree is the number of edges incident to it.
Notes
- The graph does not contain duplicate edges.
- Self-loops are not allowed.
- You may choose not to add any edge.
Goal
Return true if it is possible to make all node degrees even, otherwise return false.
Input Format
n: number of nodesedges: list of undirected edges, where each edge is a pair[u, v]
The graph is 1-indexed.
Output Format
Return true if all node degrees can be made even by adding at most two valid edges. Otherwise return false.
Constraints
- The graph is undirected and simple
- You may add at most two edges
- Added edges must connect two distinct nodes
- An added edge cannot already exist in the graph
(Exact platform constraints are not provided; these are the intended problem conditions.)
Example 1
Input
n = 5, edges = [[1,2],[2,3],[3,4]]
Output
true
Explanation
Current degrees are [1,2,2,1,0]. Nodes 1 and 4 are odd. Adding edge [1,4] makes all degrees even.
Example 2
Input
n = 4, edges = [[1,2],[2,3]]
Output
false
Explanation
This example is intentionally illustrative rather than platform-verbatim.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.