GRAPH THEORY

Question

Let G be an undirected graph on n nodes. Any two of the following statements implies the third. Is it true or False?

1. G is connected.

2. G doesn't have cycles.

3. G contain n-1 edges.

Answer 1

If G be an undirected graph on n nodes.

Any two of the following statements implies the third. It is true.

In fact these are the definition of a TREE.

G is connected & G doesn't have cycles --> G contain n-1 edges.

G is connected & G contain n-1 edges -->  G doesn't have cycles

G doesn't have cycles & G contain n-1 edges --> G is connected