更新1:
m<=5(n-2)/3 reads: m is smaller than or equal to 5(n-2)/3.
graph theory, prove problem.
2010-02-11 4:12 pm
use euler's formula to prove: if G is a connected planar graph of girth 5 then, with the above notation, m<=5(n-2)/3. deduce that the petersen graph is non-planar.
回答 (1)
2010-02-11 9:12 pm
✔ 最佳答案
In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.By, Euler theorem, V-E+F=2.E-F=V-2.Since each face has at least 5 edges and one edge can at most contributes two faces. So F<=2m/5
That is m-2m/5 <= (n-2)
3m/5 <= (n-2)
m <=5(n-2)/3
收錄日期: 2021-04-26 14:04:10
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20100211000051KK00375