CHAPTER 2: Walks

Question 1

WALK

Answer 1

let G be a simple graph. a sequence of vertices v_!,.., v_nsuch that v_i is adjacent to v_{i+1}

Question 2

CONNECTED

Answer 2

craft g is connected if for any two vertices v and w there is a walk from v to w

Question 3

TRAIL

Answer 3

walk with no repeated edges

Question 4

PATH

Answer 4

walk with no repeated vertices

Question 5

BIPARTITE GRAPH

Answer 5

a graph is bipartite if we can colour every Vertex either blue or red so that every Edge is between a blue and red vertex

edges only between two groups

•—○
•–○ •---○ ○

Question 6

complete bipartite graph

Answer 6

Every vertex is connected
bipartite graph

For each red vertex can connect to n blue vertices so nm edges in complete bipartite graph

Question 7

K_{m,n}

Answer 7

K_{m,n} consists of m+n vertices (m red, n blue) and an edge between any red vertex and any blue vertex

complete bipartite graph

For each red vertex can connect to n blue vertices so nm edges in complete bipartite graph

Question 8

C_4

Answer 8

C_4 (cycle graph) is complete bipartite graph also
isomorphic to K_{2,2}

refined isomorphism by labelling alternating colours

Question 9

C_5

Answer 9

C_5 is not bipartite: not possible to label one red alternating one blue such that only either red or blue

Question 10

when is cycle graph C_n bipartite graph

Answer 10

we must alternate between red and blue hence we must have an even number of vertices

Question 11

Lemma bipartite and cycles

Answer 11

a graph G is bipartite if and only if it doesn’t have any cycles of odd length

ie it doesn’t have a subgraph of the form C_{2k+1}

Question 12

LEMMA
PROOF
a graph g is bipartite if and only if it doesn’t have any cycles of odd length

ie it doesn’t have a subgraph of the form C_{2k+1}

Answer 12

Bipartite implies no odd cycles:
subgraphs of B_i are b_i

we must alternate between red and blue hence we must have an even number of vertices
……

and no odd cycles implies bipartite:

suppose G has no odd Cycles. Pick one Vertex V as RED any immediately adjacent have to be BLUE and any immediately adjacent to these must be RED. If G is bipartite anything of odd distance from V is BLUE and even distance is RED.

Question 13

DISTANCE

Answer 13

let G be connected and let v,w be 2 vertices.

The DISTANCE from v to w is the least number of edges in any walk from v to w

Question 14

distance if not biparite

Answer 14

if not bipartite then there exists and even path from red to Blue ie an odd cycle

there is a danger of choosing a pathway to you that Mrs out vertices from in between but contradictions allow us to see when it’s not bipartite rather than when it is bipartite

Question 15

FOREST

Answer 15

a forest is a graph without Cyclesa forest is a graph without Cycles

eg diagram a forest of three trees

Question 16

TREE

Answer 16

a tree is a connected graph without Cycles

“trees have enough edges:theyre connected”
“trees don’t have too many edges: no Cycles”

Question 17

equivalent statements for a graph G with n vertices

Answer 17

1) G is a tree
2) there is a unique path in G between any two vertices
3) G is connected and has n-1 edges
4) G has no Cycles and n-1 edges
5) G is connected but removing any Edge disconnect G
6) G has no Cycles but adding any Edge creates a cycle

Question 18

LEAF

Answer 18

let T be a tree. A Vertex V in T is a leaf if d(v)=1 / degree 1

ie only one edge

Question 19

LEMMA trees and leaves

Answer 19

let’s be a tree with 2 ≤n ≤ ∞ vertices. Then T have at least two leaves.

proof:
pick and edge if no Loops so never return and finitely many vertices so we can’t go on forever: if we get stuck that’s a leaf

Question 20

Lemma tree vertices and edges

Answer 20

if T is a tree with n vertices, then T has n-1 edges

proof: Base n=1 has no edges

inductive step: Assume m less than n and T’ a tree with m vertices. Then T’ has m-1 edges

Let T have n vertices. SInce n bigger than 1 T has a leaf V by lemma.

if V is a leaf (with only one edge e) we can make a new graph T’ by deleting v and e- claim T’ is a tree.

(We show its connected and no cycles.)

T’ connected:
T assumed connected so any 2 vertices u and w have a unique path between them. This is also a path in T’ since we only deleted edge e which went to vertex v.

T’ no loops:
T’ has no cycles as C_n ⊆ T’ ⊆ T
(subgraph of T’ is a subgraph of T)
So if T’ had a cycle T would, but T is a tree (no cycles).

Hence we deleted v and edge next to it, e, for a new tree T’.
T’ has n-1 vertices so n-2 edges, so T has n-1 edges.

( since T’ has less than n vertices we can use inductive hypothesis. T* had n -1 vertices and it’s a tree
implies
T’ had n -2 edges. T has 1 more Edge than T’ so has n - 1 edges)

Question 21

connected graph with n vertices and n-1 edges

Answer 21

If G is a connected graph with n vertices and n-1 edges then G is a tree

proof:

By induction on n. Base case n=1:
Find a Vertex of degree one delete it and Edge next to it. (But don’t know if it’s a tree. Need a different way to find a Vertex of degree 1)

inductive step: assume preposition true for all graphs with n -1 vertices

We use the handshaking lemma to show G must have a Vertex V of degree 1.

connected and more than one Vertex so we don’t have any vertices of degree 0 d(v)=0

want to prove we have a Vertex of degree 1. Assume for contradiction that are none. So every Vertex has degree d(v) ≥ 2.
we have n-1 edges so hand shaking lemma implies
2(e) = sum of v [d(v)]
2e= 2n-2 = sum of v [d(v)] bigger than sum of v[2] = 2 #vertices = 2n

contradiction as 2n-2 is not bigger than 2n.

let G have n vertices, n-1 edges and be connected. We show it has no Loops to show it’s a tree.

Base case n=1
inductive step: we saw G had a Vertex of degree 1 let this be V. Let e be The Edge connecting it.

One less Vertex and Edge. G’ is connected with n - 1 vertices and n-2 edges. This implies G’ is a tree.

So G is a tree.

Question 22

Atom valency

Answer 22

Atom: C/N/O/H
Degree: 4/3/2/1

for carbon we don’t label Vertex, hydrogen isn’t drawing but it is inferred for degrees

Question 23

ISOMER

Answer 23

graph with same degree sequence

eg H_2O has only 1 isomer

eg butane and isobutane same formula different graph

Question 24

ALKANE

Answer 24

molecule with formula C_n H_{2n+2}

e.g

methane CH_4
ethane C_2 H_6
propane C_3H_8

Question 25

LEMMA alkanes

Answer 25

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

Question 26

How many isomers does C_5H_12 have?

Answer 26

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

Question 27

Is C_2SOH_5 a tree?

Answer 27

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

Question 28

Eulerian walks intro

Answer 28

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

Question 29

EULERIAN CYLCE

Answer 29

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.

Question 30

Lemma: eulerian

Answer 30

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.

Question 31

THEOREM EULER

Answer 31

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

Question 32

THEOREM EULER

proof example:

Answer 32

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

Question 33

Semi-eulerian

Answer 33

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

Question 34

THM semi eulerian graphs

Answer 34

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

Question 35

EXAMPLE: finding an eulerian path for graph Γ

[h]--[i]---[j]
 |  /  |     |
[e]--[f]  [g]
  |       /  |   \
[a]--[b]  [c]--[d]

st labelled

Answer 35

[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

Question 36

Hamiltonian

Answer 36

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

Question 37

hamiltonian notes:

Answer 37

• 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

Question 38

THM: hamiltonian

Answer 38

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

Question 39

Lemma: hamiltonian and bipartite

Answer 39

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)

Question 40

WE CAN LOOK AT A PART OF A GRAPH:

Answer 40

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

Question 41

Petersen graph thm

pentagon with star inside

Answer 41

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.

Question 42

THM ORE

Answer 42

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.

Question 43

NOTE:

Answer 43

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

C_5

Question 44

THM

PROOF of

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

Answer 44

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

Question 45

note eulerian: iff not true

We do have connected and every vertex even degree implies Eulerian

Answer 45

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.

Question 46

Examinable proofs

Answer 46

See website

Even degree iff Eulerian

Question 47

EULERS THEOREM proof:

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

Answer 47

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

Question 48

Eulers theorem

Answer 48

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

Question 49

EULERIAN GRAPH PROOF

a connected graph G is Eulerian if and only if every Vertex of G has even degree

Answer 49

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