Introduction

This problem is often called the Even Tree problem: given a tree with an even number of nodes, remove as many edges as possible so every connected component in the remaining forest has an even number of nodes. The useful insight is local rather than global. An edge can be removed exactly when the subtree below that edge has an even number of nodes.

Why Subtree Size Is the Whole Problem

Consider an edge from a parent node to a child subtree. If the child subtree has an even number of nodes, cutting that edge produces one component of even size below and leaves an even number of nodes above as well, because even minus even is still even.

That means the decision for each candidate edge depends only on one value: the size of the child subtree.

Build the Tree and Run DFS

A depth-first search is the natural way to compute subtree sizes.

1from collections import defaultdict
2
3
4def max_removable_edges(n, edges):
5    graph = defaultdict(list)
6    for u, v in edges:
7        graph[u].append(v)
8        graph[v].append(u)
9
10    removed = 0
11
12    def dfs(node, parent):
13        nonlocal removed
14        size = 1
15
16        for neighbor in graph[node]:
17            if neighbor == parent:
18                continue
19
20            child_size = dfs(neighbor, node)
21            if child_size % 2 == 0:
22                removed += 1
23            else:
24                size += child_size
25
26        return size
27
28    dfs(1, 0)
29    return removed
30
31edges = [
32    (2, 1),
33    (3, 1),
34    (4, 3),
35    (5, 2),
36    (6, 1),
37    (7, 2),
38    (8, 6),
39    (9, 8),
40    (10, 8),
41]
42
43print(max_removable_edges(10, edges))

The DFS returns the size of each subtree. When a child subtree size is even, the connecting edge is counted as removable and that even child does not contribute to the parent's retained size.

Why the Greedy Cut Is Safe

This looks greedy because the algorithm cuts the edge as soon as it sees an even subtree. That is safe because parity makes the choice independent. You are not sacrificing a better later cut. Once a subtree is even, separating it cannot break the evenness condition in the rest of the tree.

This is what makes the problem simpler than many graph partitioning tasks. The proof comes directly from parity, not from trial and error.

Rooting the Tree Is Only a Traversal Device

The input tree is undirected, but the DFS needs a parent-child view to define subtrees. Picking node 1 as the root is only a traversal convenience. It does not mean that node 1 is special in the original graph, and it does not change the maximum number of removable edges.

That distinction matters because people sometimes worry that choosing another root could produce a different answer. It does not.

Trace a Small Example Mentally

Suppose a child subtree contains nodes 8, 9, and 10. That subtree has size 3, so you cannot cut it. If another child subtree has nodes 4 and 11, it has size 2, so the parent-child edge above it is removable.

This mental model is a good debugging tool. Every removable edge should correspond to a child subtree whose size is even when viewed from the chosen root.

Complexity and Constraints

The DFS visits every node once and each edge a constant number of times. Because a tree with n nodes has n - 1 edges, the runtime is O(n) and the memory use is O(n) for the adjacency list and recursion stack.

That is optimal for this problem because you must inspect the whole tree at least once.

Handle Practical Issues in Implementations

In coding challenges, recursive DFS is usually accepted. In production code or very deep trees, recursion depth can become a problem. An iterative post-order traversal avoids that limit, but the underlying idea stays the same: compute child subtree sizes before deciding whether to cut the edge above them.

Also make sure the input really is a tree. If the graph contains cycles or disconnected components, the parity logic alone is not enough because the problem assumptions have changed.

Common Pitfalls

• Trying to cut edges before computing subtree sizes.
• Forgetting to skip the parent during DFS in an undirected graph.
• Thinking the chosen DFS root affects the final answer.
• Returning the wrong subtree size after counting a removable child edge.
• Ignoring the requirement that the total number of nodes must be even for the task to make sense.

Summary

• The problem reduces to subtree-size calculation.
• Remove an edge when the child subtree size is even.
• A single DFS solves the problem in linear time.
• Rooting the tree is only a traversal technique, not a change to the graph.
• The parity argument is the reason the greedy cut is correct.