Solution: Graph Valid Tree

Statement

Given n as the number of nodes and an array of the edges of a graph, find out if the graph is a valid tree. The nodes of the graph are labeled from $0$ to $n - 1$, and $edges[i] = [x, y]$ represents an undirected edge connecting the nodes $x$ and $y$ of the graph.

A graph is a valid tree when all the nodes are connected, and there is no cycle between them.

Constraints:

• $1 \leq$ n $\leq 1000$
• $0 \leq$ edges.length $\leq 2000$
• edges[i].length $= 2$
• $0 \leq$ $x$, $y$ $<$ n
• $x$ $!=$ $y$
• There are no repeated edges.

Solution

For the graph to be a valid tree, the number of edges must equal $n - 1$. If the total number of edges is less than $n - 1$, not all the graph nodes are connected, which defies the property of a tree. Similarly, more edges will mean that there is a cycle in the graph; Therefore, it is not a tree.