## dan815 one year ago Graph Theory Review http://prntscr.com/8oyhbn

1. dan815

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

2. Empty

One Mississippi...

3. dan815

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

4. dan815

|dw:1444270569479:dw|

5. dan815

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

6. Empty

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

7. dan815

ohh okay cycle hehe

8. dan815

why dont they just say that hehe

9. Empty

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

ok great

11. dan815

lets try to prove this lemma

12. Empty

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

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

i hate proofs like this dan

15. dan815

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

i know its obvious lol but

17. dan815

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

18. Empty

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

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

20. Empty

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

|dw:1444271858604:dw|

22. dan815

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

23. dan815

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

24. dan815

|dw:1444272096126:dw|

25. dan815

a loop is seen as a 2 degree connection

26. dan815

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

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

28. dan815

okay lets show this is true

29. Empty

Ok sure, makes sense how would we prove this

30. dan815

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

31. Empty

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

ya lol

33. Empty

\[\Huge\square\]

34. dan815

hahahaha

35. dan815

"HUDE BOX"

36. dan815

no OKAY LEMME SEE what else they say

37. Empty

ok haha

38. dan815

okay next

39. dan815
40. dan815

okay same thing

41. dan815

hmm but why did they ask this

42. dan815

oh wait its not obvious

43. dan815

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

44. Empty

What does it mean to be a Connected Graph?

45. dan815

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

46. dan815

connected means all the vertices are connected together no isolated vertices

47. dan815

|dw:1444272700171:dw|

48. dan815

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

49. dan815

then its a connected graph

50. Empty

Ahh ok gotcha.

51. dan815

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

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

for example

54. Empty

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

|dw:1444273055412:dw|

56. Empty

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

what do u mean split every vertex apart

58. Empty

|dw:1444273207762:dw|

59. dan815

ah thats nice :)

60. Empty

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

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

lets do quantum stuff yeah

63. dan815

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

64. dan815

hold on ill find em leme close this

65. anonymous

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

66. dan815

sec im tryna do something rn