## 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

1. dan815

|dw:1442641065902:dw|

2. zzr0ck3r

is this for finite graph?

3. dan815

any graph i have like a proof but its not legit

4. zzr0ck3r

If so then we can use the fact that $$|E(G)=|V(G)|-1$$

5. dan815

its not a critical tree

6. dan815

i said begin with some vertex of odd degree |dw:1442642252949:dw|

7. dan815

oh i see okay i like that

8. 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.

9. dan815

what is the definitio nof a finite tree?

10. zzr0ck3r

finite vertices

11. zzr0ck3r

but in a tree finite edges mean finite vertices

12. zzr0ck3r

And the edges must be finite to prove they are odd.

13. 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

14. dan815

induction to prove V(G)=E(G)+1

15. dan815

for any tree

16. zzr0ck3r

Yeah, or just start constructing one, and say "by induction obviously"... lol

17. dan815

ok gotcha

18. dan815

thanks

19. zzr0ck3r

That one should be a main theorem for any section on trees in a graph theory book.

20. 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

21. dan815

sometimes i feel like they care too much about thsee proofs like some of this stuff should not require a proof xD

22. dan815

like if u are not making a cycle, u are adding one extra vertex for every single edge

23. dan815

my prof should be happy with that statement itself -.-

24. zzr0ck3r

writing correct proofs is important though :)