CHAPTER 1: Intro Flashcards
DEF 1.1.3
Def of graph
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}}
DEF 1.1.5 COMPLETE GRAPH
K_n
graph on n vertices, with an edge between any 2 distinct vertices
DEF 1.1.6 EMPTY GRAPH
E_n
graph on n vertices with no edges
DEF 1.1.7 CYCLE GRAPH
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}}
DEF 1.1.8 COMPLEMENT
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
Complement note
the empty graph and complete are complements of each other: K_n ^c = E_n
DEF 1.2.1
degree
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
DEF 1.2.8
REGULAR GRAPH
A graph Γ is d-regular or regular of degree d if every vertex v ∈Γ has the same degree d d(v)=d
regular examples
the CYCLE graph C_n is 2-regular
the COMPLETE graph K_n is (n-1) regular
the PETERSEN graph is trivalent
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?
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
THM 1.2.9 EULER’S HANDSHAKING LEMMA
Σv∈V(G) d(v) = 2|E(G)|
the graph does not need to be simple but simplicity maybe implied in the question
PROOF
THM 1.2.9 EULER’S HANDSHAKING LEMMA
Σv∈V(G) d(v) = 2|E(G)|
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
COMMON EXAM QUESTIONS
INSTANT INSANITY
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
INSTANT INSANITY as a graph
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
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
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
Instant insanity solution;
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
SUBGRAPH
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
graph isomorphism
*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
Example: C_5
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
ISOMORPHISM SHOW
*we Show isomorphic by writing down isomorphism
ISOMORPHISM FIND
*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φ
NOT ISOMORPHISM
*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
EXAMPLE: are these graphs isomorphic
- 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
REGULAR
a graph is Regular if every degree is the same
PATH graph
the path graph P_n
has n vertices with an edge between i and i+1 (not n and 1)
the cycle graph
the cycle graph has n vertices {1,2,…,n} with an edge between
i and i+1
and
n and 1
Obligatory petersen graph
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
Definition of an Isomorphism.
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
when is a graph not hamiltonian
from even just a portion of a graph we can see it is not hamiltonian if there exists a closed four cycle
