Undirected Graph Tree Validation (Medium) — Practice with Code Visualizer

You are given an undirected graph consisting of n vertices, labeled from 0 to n - 1. You are also provided with a collection of edges, where each edge is represented as a pair [uᵢ, vᵢ], indicating a bidirectional connection between vertex uᵢ and vertex vᵢ.

Your task is to determine whether this graph constitutes a valid tree structure.

A valid tree is defined as an undirected graph that satisfies the following properties:

Connectivity: Every vertex must be reachable from every other vertex through some path of edges. In other words, the graph must form a single connected component.
Acyclicity: The graph must contain no cycles. A cycle would be a path that starts and ends at the same vertex without retracing any edge.

These two properties together mean that a tree with n nodes must have exactly n - 1 edges, forming a minimally connected structure with no redundant connections.

Return true if the given graph forms a valid tree, and false otherwise.

The graph has 5 vertices and 4 edges. All vertices are connected (you can reach any vertex from any other), and there are no cycles. Vertex 0 acts as a hub connecting to vertices 1, 2, and 3, while vertex 1 connects to vertex 4. This forms a valid tree structure.

Although all 5 vertices are connected, there is a cycle present: 1 → 2 → 3 → 1. The edges [1,2], [2,3], and [1,3] form a triangle, which violates the acyclicity requirement of a tree. Additionally, there are 5 edges for 5 nodes, which exceeds the n-1 edge requirement for a tree.

The graph has 3 vertices connected in a simple linear chain: 0 — 1 — 2. With exactly 2 edges for 3 nodes (satisfying n-1 edges), all nodes are connected without any cycles, forming a valid tree (specifically, a path graph).