|
|
Proginoskes 작성:
> mina_world wrote:
> > 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.
> > [followed by an attempted proof]
>
> Why not try the contrapositive:
>
> If G has at most one cycle, then the average degree is <= 2.
>
> Proof: Handshaking Lemma, and two cases: No cycles, exactly one cycle.
> Hint for second case: If you remove a single edge from a graph with
> exactly one cycle, you get ...
yes, good idea.
suppose that G contains exactly one cycle.
if i remove a single edge from cycle,
this is a tree.
so, i can apply the property with v-e = 1.
so,
the "mean" of degrees of vertices =
[sum{i=1 to n} d(x_i)] / n = 2*e+2 / n
(e is the number of edges of tree, and
+2 induced from the removed edge.)
= 2*(v-1)+2 / n
= 2v / n
= 2n / n = 2.
> Nice problem. It looks like homework; where did you find it?
i finded in the web-site.
thank you very much.
|
|