Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Graph Theory Question #2
Replies: 2   Last Post: Apr 30, 2005 2:06 PM

 Messages: [ Previous | Next ]
 Bill Posts: 31 Registered: 4/30/05
Re: Graph Theory Question #2
Posted: Apr 30, 2005 1:49 PM

I can't believe how horrible my grammar was!! Here goes with the corrections
I should have made prior to anxiously hitting the "send" button . . .

Hi Guys:

I made a little more progress on this one. I'll tell you my thoughts
afterward:

" Let G be a graph with v vertices, such that the average vertex degree of G
is strictly >2. Prove that G must contain at least two different cycles.
"Here "different" means that they are not identical; they may share some
edges or vertices"

Alright. Firstly, I starting drawing a tree and came up with a couple of
conlusions:

1. Since he used the word "average" this means the sum of the degrees
divided by the sum of the vertices. This quotient has to be bigger that 2.

2. I can connect vertices to edges all day long either in a straight line or
a
tree, but until I connect 1 preexisting vertex to another the sum of degrees
never gets to be twice the sum of the vertices or bigger.

So anyway guys, it makes total sense to me when I play with it or draw some
pictures, but I'm having trouble wording the proof.

Appreciate it,

Bill

"Bill" <ronin68@REMOVETHISTOMAILoptonline.net> wrote in message
news:87Lce.21084\$RP1.7648@fe10.lga...
> Hi Guys:
>
> I made a little more progress on this one. I'll tell you my thoughts
> afterward:
>
> " Let G be a graph with v vertices, such that the average vertex degree of
> G is strictly >2. Prove that G must contain at least two different cycles.
> "Here "different" means that they are not identical; they may share some
> edges or vertices"
>
> Alright. Firstly, I starting drawing a tree and came up with a couple of
> conlusions:
>
> 1. Since he used the word "average" this means the sum of the degrees
> divided by the sum of the vertices. This quotient has to be bigger that 2.
>
> 2. I can drawing vertex to edge all day long either in a straight line or
> a tree, but until I can 1 preexisting vertex to another the sum of degrees
> never gets to be twice the sum of the vertices or bigger.
>
> So anyone guys, it makes total sense to me when I play with it or draw
> some pictures, but I'm having trouble wording the proof.
>
> Appreciate it,
>
> Bill
>

Date Subject Author
4/30/05 Bill
4/30/05 Brian M. Scott