dan815
  • dan815
Graph Theory A tree is a graph(set of vertices and edges) with no cycles ( no loops), show that if all the degrees of vertices is odd then the number of edges is odd
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
dan815
  • dan815
|dw:1442641065902:dw|
zzr0ck3r
  • zzr0ck3r
is this for finite graph?
dan815
  • dan815
any graph i have like a proof but its not legit

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

zzr0ck3r
  • zzr0ck3r
If so then we can use the fact that \(|E(G)=|V(G)|-1\)
dan815
  • dan815
its not a critical tree
dan815
  • dan815
i said begin with some vertex of odd degree |dw:1442642252949:dw|
dan815
  • dan815
oh i see okay i like that
zzr0ck3r
  • zzr0ck3r
First note that we must have a finite graph if we are to talk about parity in edges(unless we have infinite vertices and finite edges...stupid). We will assume it is finite. Now, \(\sum_{v\in V(G)}deg(v)=2|E(G)|\) Since the sum of the degrees is an even number, it must be that there are an even amount of vertices (each degree is odd). So, since \(|E(G)|=|V(G)|-1\) for finite trees, it must be that \(|E(G)|\) is an odd number.
dan815
  • dan815
what is the definitio nof a finite tree?
zzr0ck3r
  • zzr0ck3r
finite vertices
zzr0ck3r
  • zzr0ck3r
but in a tree finite edges mean finite vertices
zzr0ck3r
  • zzr0ck3r
And the edges must be finite to prove they are odd.
zzr0ck3r
  • zzr0ck3r
in general when we talk size of graph we talk about vertices I think it is because you can have infinite vertices and finite edges but not the other way around
dan815
  • dan815
induction to prove V(G)=E(G)+1
dan815
  • dan815
for any tree
zzr0ck3r
  • zzr0ck3r
Yeah, or just start constructing one, and say "by induction obviously"... lol
dan815
  • dan815
ok gotcha
dan815
  • dan815
thanks
zzr0ck3r
  • zzr0ck3r
That one should be a main theorem for any section on trees in a graph theory book.
zzr0ck3r
  • zzr0ck3r
if not I am sure it is easy to find on google... Normally I use strong induction on graph theory. I find it fits more often
dan815
  • dan815
sometimes i feel like they care too much about thsee proofs like some of this stuff should not require a proof xD
dan815
  • dan815
like if u are not making a cycle, u are adding one extra vertex for every single edge
dan815
  • dan815
my prof should be happy with that statement itself -.-
zzr0ck3r
  • zzr0ck3r
writing correct proofs is important though :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.