CHAPTER 2: Walks Flashcards

Question

LEMMA alkanes

Answer 1

any alkane is a tree Any molecule C_n H_{2n+2} is a tree proof: we show graph is connected and has one less Edge than vertices: *connected - it's a molecule * # vertices n + 2n+2 = 3n+2 by counting atomss * # edges by handshaking 2e = sum of d(v)'s = 4(#carbon) + 1(#hydrogen) = 4n+2n+2=3n+1 (4n+2n+2)/2 = 3n+1 edges (carbon has degree 4 hydrogen 1) SO its a tree

Answer 2

we know its a tree. case by case taking the length of the longest carbon path, and the highest degree by looking at the carbon atoms only. ``` degree 4: c | c-c-c | c degree 3: c-c-c-c | c ``` degree 2: c-c-c-c-c so total isomers: 3 isomers

Answer 3

``` its connected #vertices is 2+1+1+5=9 #edges by hand shaking 2E= sum of d(v) 2E= 24+3+2+5=8+10=18 E=9 NOT A TREE ``` as has same # edges and vertices and is a cycle ``` drawing eg has one cycle H H H | | / H-C-C-S \ / \ O H ```

Answer 4

representing city as graph Γ_k bridges = edges, sections=vertices same start as end=closed walk, every edge only once=trail

Answer 5

Let G be a graph. An Eulerian Cycle is a closed walk that uses every edge of G exactly once. If G has an eulerian cycle G is eulerian. A graph is eulerian if it has a closed walk that uses every edge exactly once.

Answer 6

if she is Eulerian, then every Vertex has even degree sketch proof: every time a walk visits v, pair the edge it arrives with the edge it leaves by.

Answer 7

a connected graph G is Eulerian if and only if every Vertex of G has even degree ⇒ by lemma ⇐ find a closed walk by picking a Vertex and start walking randomly. v-w: arrive at w by one edge so needs to be another edge to leave but degree deg(u) is even. remove edges in cycle: (for smaller graph) deleting an even # edges from each vertex so each vertex still has even degree. But each connected piece has fewer edges. By induction can find walks for them. By induction each connected piece is Eulerian. Glue cycles back together. *find a closed walk, delete Vertex, all left are small edges by induction. Then glue back together

Answer 8

Graph given as example graph with 9 vertices, 3x3 arrangement with border edges, grid edges and 2 diagonal (from middle top to end middle and from middle start to bottom middle) ``` abc •-•-• | | \| •-•-•def | \| | •-•-• ghi ``` we find a closed walk: ???? dghebfba(d) left cycles: hif blue cycles: bcfihdb

Answer 9

if it has (not necessarily closed) walk using every edge exactly once. Does Not have to be a closed walk/ drawing without lifting pen if it doesnt have to be closed but we must use every edge we may have 2 vertices (start and end) with odd degree handshaking 2e=sum of degrees RHS is even so there is an even number of vertices with odd degree

Answer 10

A connected graph G is semi-EUlerian if and only if it has at most 2 vertices of odd degree.

Answer 11

``` [h]--[i]--[j] | / | | [e]--[f] [g] | / | \ [a]--[b] [c]--[d] We choose a cycle that doesn't use every edge aeijgba for example. ``` To extend our cycle to an Eulerian cycle we delete all the edges used in the graph and for our remaining graph we find eulerian cycles. So parts of Γ missed by walk aeijgba: ``` [h]--[i] | | [e]--[f] [g] | \ [c]--[d] ``` ehif and gcd Gluing together: Follow initial cycle that wasn't eulerian and first time we hit a vertex in one of the other cycles we insert the cycle before continuing along original. SO our Eulerian cycle is: a(ehif)eij(gcd)ba

Answer 12

if it has a closed walk that uses every Vertex exactly once (hamiltonian cycle)

Answer 13

* the cycle graph C_n is hamiltonian * any graph from C_n by adding edges is hamiltonian * the path graph P_n is not hamiltonian * proving a graph isn't hamiltonian is hard i.e. we must check all possible paths

Answer 14

if we remove a Vertex from D_20 it is no longer hamiltonian proof: Suppose D_20 was Hamiltonian. At every vertex exactly 2 edges used in cycle. Suppose certain edge in cycle: other edges must be in/out of cycle. By iterating: Edges cant make a smaller cycle

Answer 15

if G is bipartite and hamiltonian, then G has the same #red and # blue vertices proof: the vertices in the hamiltonian cycle alternate red and blue. Hamiltonian cycle contains all vertices (so must return to first colour). (if we had a bipartite graph with Hamiltonian cycle we must alternate colours)

Answer 16

we can look at part of a graph and say that the full graph that this comes from isn't hamiltonian as there exists a 4-cycle: ``` v \ / \ / a b - / \ / \ w ``` if we are to visit V, degree 2 then must use edges av and bv, similarly we must use edges aw and bw to visit w. Thus we have found a 4-cycle and thus can't visit all vertices

Answer 17

The petersen graph P is not Hamiltonian proof: Every vertex degree 3, exactly one edge meeting (extra edge) every vertex. * suppose P is Hamiltonian. The HC uses up 2 edges at each vertex. So we have one more edge meeting each vertex. 10 vertices, 15 edges: for the 10-cycle (HC) we use 10 edges label these 10 edges connecting vertices v1,..,v10 and place in cycle form placing these 5 edges (extra edges): cant go on next vertex in cycle as no multiple edges cant skip 1 or 2: P has no 3 or 4 cycles. Extra edges are straight across/chords +-1 so we have ruled out these chords, an "skip 3" ruled out ie we cant have chords joining opposite vertices as we know P has no 3 or 4 cycles. So the only possible chords are: eg v1v5 is an edge but then v6 and 5 cycle means either v6v10 or v6v2 but these form 4-cycles.

Answer 18

Let G be a simple graph with n vertices, so that for any 2 nonadjacent vertices v and w we have degree deg(v) + deg(w) ≥ n. Then G is hamiltonian. proof: "minimal criminal"-assume G is a counterexample but then adding any Edge to do makes it hamiltonian. Then G must be semi hamiltonian. (ie G satisfies the condition that for V not adjacent to W degV+degW ≥ n. adding edges to G: we either increase degrees of V and W, so condition still satisfied or make one more pair adjacent that went. this could create hamiltonian Cycles: if we did this for every possible Edge not in G that don't make it hamiltonian (G') then by adding any Edge to this graph( G') it makes it hamiltonian ie its semi hamiltonian) let V_1-V_2-...-V_n be this hamiltonian path, V_1 and V_n were not adjacent so we need to add n -2 edges to V or W ( as degV+degW ≥ n.) pigeonhole principle: let i ∈ {3,... ,n-1} with V_1 adjacent to V_1 and V_n adjacent to V_{i-1} then we have a hamiltonian path and we use the pigeonhole principle to find such an i.

Answer 19

a hamiltonian graph st deg(v) + deg(w) = 4 which is less than n=5 C_5

Answer 20

proof: Every point except start and end need even degree. Starting at odd degree walking random to other degree (odd) point. Delete this path, then use induction + giving as before. Suppose Γ is semi-Eulerian with eulerian path v_0e_1v_1e_2v_3....e_nv_n. Then at any vertex other than Start and end we pair entering and leaving edges up to even. At first v_0 path leaves along e_1 but never re-enters so v_0 odd degree, similarly never leaves v_n, find only e_n so v_n odd degree. •let u,v in G be 2 vertices of odd degree •add an edge e from u to v to get G' •in G' every vertex has even degree, so it has an eulerian cycle •delete edge e from the eulerian cycle to get an eulerian walk from u to v We reduce to eulerian case: Suppose Γ connected and vertices v and w have odd degree and all others have even degree. Then we can construct new graph Γ' by adding extra edge e=vw to Γ. Then Γ' is connected and every vertex even- which implies eulerian. Deleting added edge gives eulerian path from v to w as edges are all in Γ.

Answer 21

we don't have that a graph is Eulerian If and only if connected and every vertex has even degree eg if Γ is Eulerian and E_n is a graph with n vertices and no edges Γ U E_n is eulerian and not connected.

Answer 22

See website Even degree iff Eulerian

Answer 23

First, we show this condition is necessary. Let Γ be a connected graph, and suppose that it has an Eulerian cycle w=v0,e1,v1,…,en,vn. Let v be any vertex in Γ; we must show that v has even degree. We will do this by pairing up the edges incident to v. Since w is a closed walked, we may assume that it does not start at v. Then consider the first time that the walk w visits v – it will enter by some edge ei, and leave by some other edge ei+1. We pair these two edges up. The walk w may visit v multiple times; each time it does, it must enter from one edge, and leave from another edge. Each time the walk w visits e, we will pair up the edge the walk w entered with the edge w left by. Since by supposition the walk w uses every edge of Γ exactly once, we see that every edge incident to v will be paired up with exactly one other edge in this way, and hence v must have even degree. We now show that this condition is sufficient. That is, we suppose that every vertex of Γ has even degree; we must show that Γ has an Eulerian cycle. We will proceed by induction on the number of edges of Γ. Any connected graph with 0 edges consists of just a vertex, and hence trivially has an Eulerian cycle. Now, for the inductive step, we suppose that Γ has n edges, and further suppose that we know Euler’s theorem is true for all graphs with less than n edges – that is, suppose that every connected graph Γ with less than n edges, all of whose vertices have even degree has an Eulerian walk. We first claim that Γ has some closed trail. Start at any vertex v0. Since Γ is connected, v0 has at least one edge e1 so we start our trail with v0,e1,v1. Since every vertex has an even degree, there must be another edge out of v1, say e2 leading to v2. We continue building a trail in Γ by randomly selecting an unused edge of Γ at our current vertex. Since every vertex has even degree, and whenever our trail visits a vertex we use up edges two at a time (coming and going), we see that whenever we arrive at a vertex v, there must be another edge leaving it to continue our trail – unless perhaps we hit our starting vertex v0, where we have only used one edge up. Thus, if we randomly start building a trail we must eventually return to our starting vertex and obtain a closed trail. Now, given our graph Γ, we know it has some closed trail w. If w uses every edge of Γ, we are done. If not, we consider the new graph Γ′ obtained by deleting every edge of w (but not the vertices). Note that every vertex of Γ′ has even degree. Second, Γ′ may not be connected, but each connected component Γ′i of Γ′ has fewer edges that Γ and hence has an Eulerian tour ui by supposition. Together, w and the ui visit every edge of Γ exactly once. We can stitch them together into one closed path as follows – each ui shares at least one vertex vi with w. We trace the path w, but the first time we visit vertex vi we insert the path ui before continuing along w. □

Answer 24

A connected graph Γ (without loops) has an Eulerian cycle if and only if every vertex of Γ has even degree.

Answer 25

WILL BE ON THE EXAM!! both? a connected graph G is Eulerian if and only if every Vertex of G has even degree ⇒ by lemma ⇐ find a closed walk by picking a Vertex and start walking randomly. v-w: arrive at w by one edge so needs to be another edge to leave but degree deg(u) is even. remove edges in cycle: (for smaller graph) deleting an even # edges from each vertex so each vertex still has even degree. But each connected piece has fewer edges. By induction can find walks for them. By induction each connected piece is Eulerian. Glue cycles back together. *find a closed walk, delete Vertex, all left are small edges by induction. Then glue back together

CHAPTER 2: Walks Flashcards

(49 cards)