Reply
Sat 2 Jul, 2005 09:43 am
Hello!
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.
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.
markr
I just to thank you for your great service and help.
Janet
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace