Question about theorem with trees

53 Views Asked by At

I know the theorem:

for an undirected graph on $n$ nodes, any of the following two imply the third:

  • $G$ is connected
  • $G$ does not contain a cycle
  • $G$ has $n-1$ edges

(source)

Would it be correct to add "graph is a tree" and have any two conditions imply all four?

for an undirected graph, any of the following two imply the third:

  • $G$ is connected
  • $G$ does not contain a cycle
  • $G$ has $n-1$ edges
  • $G$ is a tree

I think this is true because, by definition, if you know it is a tree then the first two conditions are implied.

The definition of tree I am using is

An undirected graph is a tree if it is connected and does not contain a cycle

1

There are 1 best solutions below

2
On

With that definition of a tree, your formulation is correct, it's just not very useful; the definition includes the first two statements. The power of the initial theorem is that from any two of the three statements, we can conclude the third.