DscreteMth

2007-01-21 7:21 pm
Is the following statement true?
Given that G=(V,E) is a graph and suppose v1 and v2 are the only vertices with odd degree. Then there exists a path joining v1 and v2.

回答 (2)

2007-01-21 8:23 pm
✔ 最佳答案
The statement is true or not due to the definition of path
Accronding a theorem. A connected graph has an Eulerian trail iff it has at most two graph vertices of odd degree.
So, there is a trial from v1 to v2.
If the definition of path in your book is the same of the trial, then the statement is true. Otherwise, it is not true.
Accronding some books.
A path on a graph (also called a chain) is a sequence
圖片參考:http://mathworld.wolfram.com/images/equations/Path/inline12.gif
are distinct.
However, in the trial, xi and xj can be the same.
2007-01-26 6:28 pm
myisland8132's answer has many problems:
1) The question does not say the graph is connected
2) The statement is true no matter what type of path you are considering. It is because if the path has repeat V at some point: v1,.....V, .......V, ......v2, just delete every thing between V to get a simple path with no repeat vertice v1.....V.......v2

By definition, if a graph is connected, then there is a path from any point to any point.

So we want to show that v1 and v2 lie in a connected component. If not, consider the subgraph containing v1 but not v2. By assumption this graph has only v1 with odd degree. This is impossible because in any graph, every edge contributes two degree, so the total degree of a graph is even.

2007-02-11 02:42:24 補充:
咁係錯o既答案選左都冇計...
參考: PhD Math


收錄日期: 2021-04-13 17:08:03
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20070121000051KK01244

檢視 Wayback Machine 備份