261. Graph Valid Tree

• 261. Graph Valid Tree
  • Description
  • Proof
  • Solution

Description

Here

Proof

Definition of tree:

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa.

Key: Every acyclic connected graph is a tree, and vice versa.

Interesting:

A tree is an undirected graph G that satisfies any of the following equivalent conditions:

• G is connected and has no cycles.
• G is acyclic, and a simple cycle is formed if any edge is added to G.
• G is connected, but would become disconnected if any single edge is removed from G.
• G is connected and the 3-vertex complete graph K3 is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

• G is connected and has n − 1 edges.
• G is connected, and every subgraph of G includes at least one vertex with zero or one incident edges. (That is, G is connected and 1-degenerate.)
• G has no simple cycles and has n − 1 edges.

Solution

Here, we need verify 2 things:

1. No cycle
2. Has n - 1 edges