|
|
hello sir~
G is a simple connected graph.
the "mean" of degrees of vertexs is bigger than 2.
(namely, > 2)
show that G contains at least two cycles.
-------------------------------------------------
um... i think...
hand-shaking lemma)
2e = sum_i d(x_i)
(e is the number of edges,
d(x_i) is the degree of vertex x_i.)
let the number of vertexs be n.
if G does not contain the cycle,
G is a tree diagram.
so, v-e = 1.
(v is the number of vertex,
e is the number of edges).
so,
the "mean" of degrees of vertexs =
[sum{i=1 to n} d(x_i)] / n = 2e / n =
2(v-1) / n = 2(n-1) / n < 2.
thus contradiction.
if G only contains one cycle,
..............
i can't deduce a contradiction.
so, i need your advice.
|
|