If G is connected and order = size - 1 G is a Tree

Question

to prove that, is it correct to proceed by contradicion and try to reach some conclusion like "if the order = size - 1 there can't be any cycles"? In that case, can you give me a hint of where to start?

EDIT: Sorry for not providing enough details. I am considering simple graphs. the definition of tree I use is "connected and acyclic graph", so an equivalent thing to prove would be if G has n - 1 edges, it has no cycles.

thanks!

Answer 1

I would prove one direction of this theorem by induction on $V$, the number of vertices in $G$. Start off with a single point, which is $V = 1$, $E = 0$. Assume true up to $V = n$. For the inductive step, we assume the tree has $n$ vertices and $n-1$ edges. What happens when you create a new vertex and connect it to the tree? Will a cycle be created? This shows that $V = n$ and $E = n - 1$ implies that the graph is a tree.

For acyclicity and connectedness implying $E = V - 1$, I would use contradiction as you described. Suppose $G$ is connected and acyclic but has fewer than $V - 1$ edges. You violate connectivity. For more than $V - 1$ edges, you get a contradiction on acyclicity.

Answer 2

If $G$ had a circuit, you could remove one of the edges from the circuit and the graph would still be connected, i.e. you would have a connected graph with $n - 2$ edges. Prove that a connected graph must have at least $n-1$ edges and you are done.