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

- dan815

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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- dan815

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

- Empty

One Mississippi...

- 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

|dw:1444270569479:dw|

- dan815

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

- Empty

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

- dan815

ohh okay cycle hehe

- dan815

why dont they just say that hehe

- 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

ok great

- dan815

lets try to prove this lemma

- 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

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

i hate proofs like this dan

- 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

i know its obvious lol but

- dan815

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

- 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

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

- 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

|dw:1444271858604:dw|

- dan815

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

- dan815

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

- dan815

|dw:1444272096126:dw|

- dan815

a loop is seen as a 2 degree connection

- 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

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

- dan815

okay lets show this is true

- Empty

Ok sure, makes sense how would we prove this

- dan815

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

- 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

ya lol

- Empty

\[\Huge\square\]

- dan815

hahahaha

- dan815

"HUDE BOX"

- dan815

no OKAY LEMME SEE what else they say

- Empty

ok haha

- dan815

okay next

- dan815

http://prntscr.com/8oypzs

- dan815

okay same thing

- dan815

hmm but why did they ask this

- dan815

oh wait its not obvious

- dan815

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

- Empty

What does it mean to be a Connected Graph?

- dan815

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

- dan815

connected means all the vertices are connected together no isolated vertices

- dan815

|dw:1444272700171:dw|

- dan815

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

- dan815

then its a connected graph

- Empty

Ahh ok gotcha.

- 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

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

for example

- 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

|dw:1444273055412:dw|

- 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

what do u mean split every vertex apart

- Empty

|dw:1444273207762:dw|

- dan815

ah thats nice :)

- 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

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

lets do quantum stuff yeah

- dan815

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

- dan815

hold on ill find em leme close this

- anonymous

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

- dan815

sec im tryna do something rn

Looking for something else?

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