Please help me check the answers to my homework
please help me with this question
Show that in every simple graph there is a path from any vertex of odd
degree to some other vertex of odd degree?
here is my answer please check and correct if its wrong thanx
ANSWER:
In a simple graph, the sum of the degrees of the vertices must always be even. Thus, if there is a vertex of odd degree, there must be another vertex of odd degree (so the sum will be even). If the graph is connected, then there is a path from any vertex to any other vertex. If it is not connected, it must be made up of connected subgraphs, and the sum of the degrees of the vertices of each connceted subgraph still has to be even – so the odd vertices in each connected subgraph must still come in pairs.
[Edited by - LessBread on March 21, 2007 8:38:56 PM]
Hyderman,
I know your homework subject is related to game development, but homework questions aren't appropriate in these forums. The Forum FAQ provides some rules, and philosophy behind this. I am afraid I must close the thread.
I know your homework subject is related to game development, but homework questions aren't appropriate in these forums. The Forum FAQ provides some rules, and philosophy behind this. I am afraid I must close the thread.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement