Year 12s: what will be the first way you research your future options? >>

Help please with a quite simple proof?

Hi, I'm struggling to do a quite simple proof from the trees, graphs and algorithms part of my course and need to know how to do this type of question for the exams. Can someone please help point me in the right direction as I don't really know how to do it? Here's the question:

Let T be a tree with n vertices.
(i) Prove that there is a unique path between any two vertices in T.
(ii) Use induction on n to prove that T has n-1 edges.
(Hint: for the induction step, remove an edge from T and consider the resulting graph.)

Thanks for any help! :smile:

Reply 1

ghostwalker

Original post by tarnat

...

What's your definition of a tree?

Reply 2

tarnat

This is what we were given:

A tree is a simple connected graph with no cycles. (i.e. no paths vertex u to itself).
A simple graph is one without loops or multiple edges.

Reply 3

msmith2512

Original post by tarnat

This is what we were given:

A tree is a simple connected graph with no cycles. (i.e. no paths vertex u to itself).
A simple graph is one without loops or multiple edges.

Suppose, for a contradiction, that the route is not unique. So there are two routes say R(1) and R(2). Now follow R(1) followed by R(2) - this is a cycle therefore contradiction so route between two points is unique.

Reply 4

ghostwalker

Original post by tarnat

...

As msmith2512 said, proof by contradiction.

Depending on your definition of a cycle (does it need to be Hamiltonian on the vertices it visits?), that proof may be enough.

(edited 11 years ago)

Reply 5

Tallon

Original post by msmith2512

It's not quite that simple because R(1) and R(2) might share a large portion on the same graph, or might split off and come back together but that's the gist of the argument anyway (where they split off and come back together is a cycle).

for (ii) I hope you don't mind me posting another really elegant (not by induction so don't worry) argument:

Spoiler

(edited 11 years ago)

Reply 6

tarnat

Thanks for the help on (i) I didn't realise I could give an answer so short.

For part (ii) I've done a few steps of the induction but I don't see how the hint can help with the inductive step? When an edge is taken away is the vertex also taken?