A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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

  • This Question is Closed
  1. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1442641065902:dw|

  2. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    is this for finite graph?

  3. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    any graph i have like a proof but its not legit

  4. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  5. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    its not a critical tree

  6. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  7. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh i see okay i like that

  8. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what is the definitio nof a finite tree?

  10. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    finite vertices

  11. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    but in a tree finite edges mean finite vertices

  12. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  13. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  15. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    for any tree

  16. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  17. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok gotcha

  18. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thanks

  19. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  20. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  22. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  24. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    writing correct proofs is important though :)

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.