CHAPTER 1: Intro

Question 1

DEF 1.1.3

Def of graph

Answer 1

A graph G consists of a set V(G) VERTICES of G

a set E(G) called the edges of G, of 2 element subsets of V(G)

*SIMPLE GRAPH:
we have defined st cant have more than one edge between any 2 vertices and no loops and symmetrics edges

*water has 3 vertices V(G)={0, H_1, H_2}

and 2 edges E(G)={{0,H_1}, {0, H_2}}

Question 2

DEF 1.1.5 COMPLETE GRAPH

Answer 2

K_n

graph on n vertices, with an edge between any 2 distinct vertices

Question 3

DEF 1.1.6 EMPTY GRAPH

Answer 3

E_n

graph on n vertices with no edges

Question 4

DEF 1.1.7 CYCLE GRAPH

Answer 4

C_n

graph on n vertices
{v_1,..,v_n}

with
edges

{{v_1,v_2},{v_2,v_3},…,{v_{n-1},v_n},{v_n,v_1}}

Question 5

DEF 1.1.8 COMPLEMENT

Answer 5

COMPLEMENT OF A SIMPLE GRAPH G,

G^c or overline(G) but
{v,w} in E(G^c)
IFF
{v,w} ∉E(G)

There is an edge between v and w in G^c IFF

there is not an edge between v and w in G

the complement of a simple graph is a graph with the Vertex set complement of adjacent vertices sets

Question 6

Complement note

Answer 6

the empty graph and complete are complements of each other: K_n ^c = E_n

Question 7

DEF 1.2.1

degree

Answer 7

vertices v is adjacent / incident to

Let G be a simple graph, and let v∈V(G) be a vertex of G. Then the degree of v

d(v)= #edges e ∈E(G) with v∈e

Question 8

DEF 1.2.8

REGULAR GRAPH

Answer 8

A graph Γ is d-regular or regular of degree d if every vertex v ∈Γ has the same degree d d(v)=d

Question 9

regular examples

Answer 9

the CYCLE graph C_n is 2-regular

the COMPLETE graph K_n is (n-1) regular

the PETERSEN graph is trivalent

Question 10

HANDSHAKING LEMMA

is it possible that everyone at the party knows exactly 3 other people? if everyone who knows shakes hands how many hand shakes?

Answer 10

Each handshake is between 2 people so #edges on graph.

So for each person knowing 3 other people:

7 people, 7 x 3 each handshake counted twice so 7x3/2 = 10.5 handshakes not possible

Question 11

THM 1.2.9 EULER’S HANDSHAKING LEMMA

Answer 11

Σv∈V(G) d(v) = 2|E(G)|

the graph does not need to be simple but simplicity maybe implied in the question

Question 12

PROOF

THM 1.2.9 EULER’S HANDSHAKING LEMMA

Σv∈V(G) d(v) = 2|E(G)|

Answer 12

counting ends of edges in two different ways.
every end occurs at a Vertex and at Vertex v there are d(v) ends. so the total number of ends is the So on the left-hand side.

on the other hand every Edge has two ends and so the number of ends is twice the number of edges, giving the right hand side

Question 13

COMMON EXAM QUESTIONS

INSTANT INSANITY

Answer 13

4 cubes, each side 1/4 colours and stacking cubes to show a sol or show none

to solve: consider what pair of faces are opposite each other?

suppose we want face one forward then we have 4 different ways to rotate the cube to keep this the same.

the same face will always appear on the opposite side but we can get any of the remaining for faces to be on top

Question 14

INSTANT INSANITY as a graph

Answer 14

each Vertex coloured B,G R or Y. Edges are between two colours each time they are opposite faces on a cube labelled 1 2 3 or 4.

12 edges and 3 labels of 1,2,3 or 4

suppose we have an arrangement that was a solution. then from each cube pick the edge representing the colours facing the front, these four edges are a subgraph of our original graph.

with one edge of each label (number 1,2,3 or 4) representing each cube, this is a solution of instant insanity each colour appears once on the front face and once on the back .

THUS each Vertex on the subgraph must have degree 2.

we have another subgraphs satisfying these two properties by looking at top and bottom for each cube these two subgraphs don’t have any edges in common:

We need a pair of subgraphs S_1 and S_2:
1) each subgraphs S_i has one Edge labelled 1,2,3 or 4

2) every Vertex of S_i has degree 2
3) no Edge the original graph is used in both S_1,S_2

Thus to show the set of Cubes does not have a solution, we need to show that the graph does not have two subgraphs satisfying one two three

Question 15

EXAMPLE: instant insanity no solution
given an impossible set

Each cube net:

down: BYBR across: GYR
down: BYGR across: YYY
down: GBYB across: GBR
down: BGGR across: YGR

Answer 15

1st cube:
loop at B

2nd cube:
edge B to G

3rd cube:
loop at B

4th cube:
edge B to G

We draw a graph, vetices B,G,R and Y and 12 edges from the nets.

B: has 2 loops (1,3) amd 2 edges to G (2,4)

G: 3 edges to R (1,3,4) and 2 edges to B (2,4) edge to Y

R: 3 edges to G and 3 to Y

Y: loop (2) , edge to G (3), 3 edges to R (1,2,4)

• a subgraph of type 1 isn’t possible as G and R don’t have loops
• (type 2) the only triangle is G-R-Y and B does have Loops. Edge Y-G must be 3 ,loop at B must be 1 so G-R is 4 and Y-R is 2: 1 subgraph (loop at B and triangle G-R-Y)

*(type 3) only option is loops at B and Y and double edge between G and R. Loop at Y is 2, one of G-R is 4 and loop at B and G-R_2 can switch between 1 and 3:
2 subgraphs: for partial Solutions

• (Type 4) only option is double edges B-G and Y-R. However none are labelled 3 so it’s not possible
• (type 5) can’t happen because be is only adjacent to G and itself: to be in a 4 cycle would have to be adjacent to two vertices that aren’t itself

therefore the instant insanity puzzle has no solution
⇔
three different possibilities for subgraphs S_1, S_2 that satisfy 1 and 2. However, all three contain the edge labelled 4 between G and R hence we cannot choose 2 with disjoint edges

Question 16

Instant insanity solution;

Answer 16

we find all graphs such that 1 and 2 are satisfied, if every Vertex has degree 2 either:

1* every Vertex has a loop
2* there is one Vertex with a loop the rest form triangles
3* there are two vertices with Loops and a double edge between other two vertices
4* there are two pairs of double edges
5* all the vertices live in one 4 cycle

Question 17

SUBGRAPH

Answer 17

a subgraph S of Γ is a graph where:
V(S) ⊂ V(Γ)
E(S) ⊂ E(Γ)

if an edge is in S than we need both its ends in S

Question 18

graph isomorphism

Answer 18

*an isomorphism of a simple graph 
φ:G→ H
is a bijection 
φ: V(G) → V(H)
between Vertex sets that preserves the number of edges between vertices.

φ(v) and φ(w) adjacent in H if and only if v & w are adjacent in G

we must have
d(φ(v))= d(v)
for all vertices vin G and bijection implies degree sequence is preserved

*we will solve the graph isomorphism problem in the exam

Question 19

Example: C_5

Answer 19

C_5 is isomorphic to its complement C_5^c

the cycle graph on 5 vertices has isomorphism

φ: C_5 → C_5 ^c
defined by 
φ(a)=a
φ(b)=c
φ(c)=e
φ(d)=b
φ(e)=d

1 is adjacent to 2 and 5,
2 is adjacent to 1 and 3 etc

drawn as a star or as cycle graph

Question 20

ISOMORPHISM SHOW

Answer 20

*we Show isomorphic by writing down isomorphism

Question 21

ISOMORPHISM FIND

Answer 21

*we find isomorphism by finding the function which preserves degree picking one Vertex v and map into any Vertex w with the degrees equal: d(v) = d(w)

adjacent vertices with map and we continue expanding

for an isomorphismφ

Question 22

NOT ISOMORPHISM

Answer 22

*we prove two graphs aren’t isomorphism by finding an obstruction for example a difference between two graphs

number of vertices
number of edges connectedness
Loops or
degree sequence

Question 23

EXAMPLE: are these graphs isomorphic

Answer 23

• degree sequences differ so some cant be isomorphic
• looking at the numbers of 3 4 and 5 Cycles
• looking at the degree sequence of adjacent vertices e.g all adjacent to a Vertex of degree 4 except one
• finally find an isomorphism

Question 24

REGULAR

Answer 24

a graph is Regular if every degree is the same

Question 25

PATH graph

Answer 25

the path graph P_n

has n vertices with an edge between i and i+1 (not n and 1)

Question 26

the cycle graph

Answer 26

the cycle graph has n vertices {1,2,…,n} with an edge between
i and i+1
and
n and 1

Question 27

Obligatory petersen graph

Answer 27

15 edges and 10 vertices.

drawn like a pentagon with a star in the middle

every Vertex has three three so this is a regular trivalent graph

the sum of every degree in the set of vertices is

2* modulus of edges

so 3(10)= 2(mod(15)) checked

Question 28

Definition of an Isomorphism.

Answer 28

Definition of an Isomorphism. An isomorphism between two simple graphs G and H is a bijection ϕ : V(G) → V(H) so that for all v, w ∈ V(G), ϕ(v) and
ϕ(w) are adjacent if and only if v, w were. Alternatively, this can be phrased as: ϕ preserves the number of edges between vertices.

Commentary on the definition. Note that we required the graph to be simple: if G has multiple edges or loops, then our definition of isomorphisms need to keep
track of some extra information. This won’t appear on the exam, but it is instructive to try to understand yourself: the graph G with one vertex and one loop (an
edge) should have two different isomorphisms from G to itself; the graph H with two vertices and two edges between them should have 4 different isomorphisms
from H to itself

Question 29

when is a graph not hamiltonian

Answer 29

from even just a portion of a graph we can see it is not hamiltonian if there exists a closed four cycle