|
|
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 ...
Nice problem. It looks like homework; where did you find it?
--- Christopher Heckman
|
|