Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


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 >



