A community for students.
Here's the question you clicked on:
 0 viewing
dan815
 one year ago
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
dan815
 one year ago
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

This Question is Closed

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2is this for finite graph?

dan815
 one year ago
Best ResponseYou've already chosen the best response.0any graph i have like a proof but its not legit

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2If so then we can use the fact that \(E(G)=V(G)1\)

dan815
 one year ago
Best ResponseYou've already chosen the best response.0its not a critical tree

dan815
 one year ago
Best ResponseYou've already chosen the best response.0i said begin with some vertex of odd degree dw:1442642252949:dw

dan815
 one year ago
Best ResponseYou've already chosen the best response.0oh i see okay i like that

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2First 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)=2E(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
 one year ago
Best ResponseYou've already chosen the best response.0what is the definitio nof a finite tree?

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2but in a tree finite edges mean finite vertices

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2And the edges must be finite to prove they are odd.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2in 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
 one year ago
Best ResponseYou've already chosen the best response.0induction to prove V(G)=E(G)+1

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2Yeah, or just start constructing one, and say "by induction obviously"... lol

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2That one should be a main theorem for any section on trees in a graph theory book.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2if 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
 one year ago
Best ResponseYou've already chosen the best response.0sometimes i feel like they care too much about thsee proofs like some of this stuff should not require a proof xD

dan815
 one year ago
Best ResponseYou've already chosen the best response.0like if u are not making a cycle, u are adding one extra vertex for every single edge

dan815
 one year ago
Best ResponseYou've already chosen the best response.0my prof should be happy with that statement itself .

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.2writing correct proofs is important though :)
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.