dan815
  • dan815
Graph Theory Review http://prntscr.com/8oyhbn
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
dan815
  • dan815
gimme a sec i gotta see which ones i have to go over
Empty
  • Empty
One Mississippi...
dan815
  • dan815
What's a 1 factor and 2 factor of this graph

Looking for something else?

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

More answers

dan815
  • dan815
|dw:1444270569479:dw|
dan815
  • dan815
i dont know if u can repeat edges in a 2 factor or not
Empty
  • Empty
|dw:1444270981730:dw| |dw:1444271018570:dw|
dan815
  • dan815
ohh okay cycle hehe
dan815
  • dan815
why dont they just say that hehe
Empty
  • 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.
dan815
  • dan815
ok great
dan815
  • dan815
lets try to prove this lemma
Empty
  • 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.
dan815
  • 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
Empty
  • Empty
i hate proofs like this dan
dan815
  • 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
dan815
  • dan815
i know its obvious lol but
dan815
  • dan815
i should practice writing this, since it might come up tmr
Empty
  • Empty
no this is why I hate proofs and rant about squares, let's do some other graph theory problem that's more fun.
dan815
  • dan815
well i gotta go over 3 other theorems in this series, they might be more involved
Empty
  • 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.
dan815
  • dan815
|dw:1444271858604:dw|
dan815
  • dan815
If a pseudograph G has an euler circuit, then G is connected and the degree of every vertex is even
dan815
  • dan815
a psedugraph is a Graph that allows multiple edges from 1 vertex to another and loops for example
dan815
  • dan815
|dw:1444272096126:dw|
dan815
  • dan815
a loop is seen as a 2 degree connection
dan815
  • 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.
dan815
  • dan815
If a pseudograph G has an euler circuit, then G is connected and the degree of every vertex is even
dan815
  • dan815
okay lets show this is true
Empty
  • Empty
Ok sure, makes sense how would we prove this
dan815
  • dan815
ull get stuck at a vertex without being able to return to your starting vertex if u dont have even
Empty
  • Empty
if you enter a point you have to leave that point so there has to be an even degree at every vertex. Proved?
dan815
  • dan815
ya lol
Empty
  • Empty
\[\Huge\square\]
dan815
  • dan815
hahahaha
dan815
  • dan815
"HUDE BOX"
dan815
  • dan815
no OKAY LEMME SEE what else they say
Empty
  • Empty
ok haha
dan815
  • dan815
okay next
dan815
  • dan815
http://prntscr.com/8oypzs
dan815
  • dan815
okay same thing
dan815
  • dan815
hmm but why did they ask this
dan815
  • dan815
oh wait its not obvious
dan815
  • dan815
u gotta show that any circuit u get is part of the euler circuit
Empty
  • Empty
What does it mean to be a Connected Graph?
dan815
  • dan815
a circuit is where u cant repeat edges, but u can repeat vertcies, for a psedugraph
dan815
  • dan815
connected means all the vertices are connected together no isolated vertices
dan815
  • dan815
|dw:1444272700171:dw|
dan815
  • dan815
Like there has to be a path between any 2 given vertices
dan815
  • dan815
then its a connected graph
Empty
  • Empty
Ahh ok gotcha.
dan815
  • 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
dan815
  • 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
dan815
  • dan815
for example
Empty
  • 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.
dan815
  • dan815
|dw:1444273055412:dw|
Empty
  • 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\)
dan815
  • dan815
what do u mean split every vertex apart
Empty
  • Empty
|dw:1444273207762:dw|
dan815
  • dan815
ah thats nice :)
Empty
  • 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:
Empty
  • 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\]
Empty
  • Empty
lets do quantum stuff yeah
dan815
  • dan815
okay i have these bunch of problems to work thru for preparation
dan815
  • dan815
hold on ill find em leme close this
anonymous
  • anonymous
@dan815 can you help me on a calculus problem please ?
dan815
  • dan815
sec im tryna do something rn

Looking for something else?

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