A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dan815

  • one year ago

Graph Theory Review http://prntscr.com/8oyhbn

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

    gimme a sec i gotta see which ones i have to go over

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

    One Mississippi...

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

    What's a 1 factor and 2 factor of this graph

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

    |dw:1444270569479:dw|

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

    i dont know if u can repeat edges in a 2 factor or not

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

    |dw:1444270981730:dw| |dw:1444271018570:dw|

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

    ohh okay cycle hehe

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

    why dont they just say that hehe

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

    all vertices must have k-degree in a k-factor. So you can see that in a 1-factor they're all matched up. Why the hell they don't say that idk but I just learned this from wikipedia just now.

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

    ok great

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

    lets try to prove this lemma

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

    There are multiple ways to 1-factor this graph but only one way to 2-factor it and of course no way to 3-factor it.

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

    A graph G is a tree if and only if there is only 1 path that exists exactly one path between any 2 vertices

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

    i hate proofs like this dan

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

    if u see an if and only if, we gotta prove both ways Show if you have a tree, then only 1 path between and 2 vertices if you have only 1 path between any 2 vertcies, its a tree

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

    i know its obvious lol but

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

    i should practice writing this, since it might come up tmr

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

    no this is why I hate proofs and rant about squares, let's do some other graph theory problem that's more fun.

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

    well i gotta go over 3 other theorems in this series, they might be more involved

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

    Alright, I can help try to figure out stuff that's not like intuitively obvious I think. But I won't try to get into proving too much, you gotta figure that part out on your own.

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

    |dw:1444271858604:dw|

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

    If a pseudograph G has an euler circuit, then G is connected and the degree of every vertex is even

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

    a psedugraph is a Graph that allows multiple edges from 1 vertex to another and loops for example

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

    |dw:1444272096126:dw|

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

    a loop is seen as a 2 degree connection

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

    An Euler circuit is a circuit that uses every edge of a graph exactly once. ▶ An Euler path starts and ends at different vertices. ▶ An Euler circuit starts and ends at the same vertex. Page 2.

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

    If a pseudograph G has an euler circuit, then G is connected and the degree of every vertex is even

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

    okay lets show this is true

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

    Ok sure, makes sense how would we prove this

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

    ull get stuck at a vertex without being able to return to your starting vertex if u dont have even

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

    if you enter a point you have to leave that point so there has to be an even degree at every vertex. Proved?

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

    ya lol

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

    \[\Huge\square\]

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

    hahahaha

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

    "HUDE BOX"

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

    no OKAY LEMME SEE what else they say

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

    ok haha

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

    okay next

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

    http://prntscr.com/8oypzs

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

    okay same thing

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

    hmm but why did they ask this

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

    oh wait its not obvious

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

    u gotta show that any circuit u get is part of the euler circuit

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

    What does it mean to be a Connected Graph?

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

    a circuit is where u cant repeat edges, but u can repeat vertcies, for a psedugraph

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

    connected means all the vertices are connected together no isolated vertices

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

    |dw:1444272700171:dw|

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

    Like there has to be a path between any 2 given vertices

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

    then its a connected graph

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

    Ahh ok gotcha.

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

    i think im done, ill just read the book for this thm!! lets do quantum stuff, i got a midterm on that too day after

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

    this one is basically just showing since its connected if u get one smaller circult u can always attach it to a bigger circuit until its an euler circuit

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

    for example

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

    I don't know what constitutes as proof. It has all even number of edges you can split every vertex apart so that only two edges touch it. Then if you find a vertex with 2 edges you can turn that into a single edge until you have just one loop left.

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

    |dw:1444273055412:dw|

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

    I don't know what constitutes as proof. It has all even number of edges you can split every vertex apart so that only two edges touch it. Then if you find a vertex with 2 edges you can turn that into a single edge until you have just one loop left. \(\Huge \square\)

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

    what do u mean split every vertex apart

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

    |dw:1444273207762:dw|

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

    ah thats nice :)

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

    Suppose though you want to prove a little deeper like, maybe a cut will sever it like this! |dw:1444273374845:dw| Proof that this will never hapen coming up:

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

    We know the graph is connected: |dw:1444273416153:dw| Now let's say we pick one arbitrary way of cutting it so that it makes the graph no longer connected, then we know since it's connected the graph looks something like this: |dw:1444273477507:dw| So we always have a way to cut two vertices apart so that the graph remains connected. \[\huge \square\]

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

    lets do quantum stuff yeah

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

    okay i have these bunch of problems to work thru for preparation

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

    hold on ill find em leme close this

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

    @dan815 can you help me on a calculus problem please ?

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

    sec im tryna do something rn

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