Graph Theory .... PLEASE HELP!

[jewelses]

Hi,

I have two questions related to Graph Theory.

Let G be a graph with n vertices. Show that the following statements are
correct:
1. If G does not contain any cycle and has exactly n-1 edges, then there is
exactly one chain between any two vertices. You may use the fact, that a
disconnected graph without cycles has at most n-2 edges.
2. If between any two vertices there is exactly one chain, then G is connected
and does not contain any cycle.

Hope you can help me.

Thanks in advance!

 

[Guido]

My Reply

1) Since a disconnected graph without cycles has at most n-2 edges, G must be connected. Since G is connected, there is at least one chain between any two vertices. If there were more than one chain between two vertices, a cycle would exist. Therefore, there is exactly one chain between any two vertices.

2) Since between any two vertices there is exactly one chain, G must be connected. If G contained a cycle, there would be at least two chains between at least two vertices. Therefore, G does not contain a cycle.