CHAPTER 4: Graphs on surfaces Flashcards
The Utilities Problem: Connect three houses ◘ to all three utilities • without crossing the lines?
◘ ◘ ◘
• • •
*we can try going around
- straight across
- diagonals but avoid intersections
failed attempts?
1 2 3
◘ ◘ ◘
• • •
x y z
cant be done
DEF: planar
A graph G is planar if it can be drawn in the plane so that no edges cross.
ie at least one drawing where edges don’t cross
What do we mean “draw” an edge?
Injective continuous map f : [0,1] →R2
urilities problem and planar:
The Utilities question becomes: Is the complete bipartite graph K3,3 planar
Is graph planar
We assume it is:
Any cycle C_n ⊂ G can be drawn as a circle.
Any edge e ∈ G,e / ∈ Cn would be inside or outside the circle
certain pairs of edges cant be on same side
Is the complete bipartite graph K3,3 planar
Theorem: K3,3 isn’t planar
Label blue ABC and red XYZ
Suppose K_{3,3} is planar. Then the Hamiltonian cycle AXBYCZA would be a circle.
edges AY,BZ,CX still need to be drawn
CASE1: AY inside cycle
- we need to draw BZ outside ( 2 ways)- either way we cant draw CX (as it intersects BZ)
CASE 2: AY outside the cycle
two ways to do this,
but either way BZ needs to be inside,
now we cant draw CX
NOTE
Very similar cases
PLANE TO SPHERE
In the plane R2: The outside and inside of a circle are different: I The inside is bounded, the outside isn’t I One way to connect inside, two ways to connect outside
BUT EASIER ON A SPHERE S^2
inside and outside of a circle look the same.
and only one way to connect outside points
Stereographic projection: S2 = R2 ∪{p}:
COROLLARY
Corollary G is planar if and only if G can be drawn on the sphere.
Proof. If: Draw G on S2; project from a point p ∈ S2 \G Only if: Project from plane to sphere
Upshot: don’t need to treat inside/outside as separate cases
The method we used to show K3,3 isn’t planar generalises
Take any cycle C in a graph G
* If the G is planar, C will be drawn as a ”circle”
- Any other vertex or edge must lie inside or outside circle
- Handle possibilities case by case
is K5 planar?
K5 isn’t planar
(because we use the stereographic projection we have that the inside is the same as the outside, so we only consider one case without loss of generality)
Use method with Hamiltonian cycle ABCDEA
- this cycle gives a circle and we need to draw 5 edges still
- we assume AC inside: then B is cut off inside so BD and BE outside
- BD cuts of C from E on outside, CE inside
- consider AD: CE cuts off inside, BE cuts off outside
Therefore K5 isn’t planar
The crossing graph packages the case by case analysis
“Edge e1 is in, so edge e2 out, so edge e3 in, so …” gets tiresome.
G a graph with Hamiltonian cycle C
Some pairs of edges in G \C cross if drawn inside C
Some pairs of edges can be drawn on the same side
DEF crossing graph cross (G,C)
G a graph with Hamiltonian cycle C
The crossing graph Cross(G,C) has: Vertices: the edges in G \C Edges e and f are adjacent if they cross inside C
THM
Theorem (Planarity Algorithm for Hamiltonian graphs)
G is planar if and only if Cross(G,C) is bipartite
ie we can only apply this if its Hamiltonian/ if there is a Hamiltonian cycle
Example of planarity algorithm:
A graph Γ/G
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
what is cross(Γ,AFIHCBEDGA)?
we redraw graph shown as a Hamiltonian cycle outside and edges inside
Hamiltonian cycle
AFIHCBEDGA
(start at I degree 2 so IF and IH used,BC,CF, BE etc)
We redraw the graph with Hamiltonian cycle as a circle-other edges inside
so we have inside edges (crossing each other) HG CF HE BA EF AD
What is Cross(Γ,AFIHCBEDGA)?
Vertices = edges in middle
Edges = crossings in middle
7 intersections from 6 lines
ie cross(G,C) isn’t bipartite so G isn’t planar
crossing graph : (depends on our Hamiltonian cycle) diagram drawn with edges of those edges which cross: [AB]--[GH] [AB]--[FE] [AB]--[EH] [EH]--[FC] [AD]--[GH] [FE]--[GH]
notes about cross and planar:
Cross(K5,123451) which is isomorphic to a five cycle:
is not bipartite. Hence, by the planarity algorithm for Hamiltonian graphs, we see that K5 is not planar.
Example of planarity algorithm:
A graph Γ/G
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
WHAT HAPPENS IF WE DELETE VERTICES FROM Cross(G,C)
If we delete AB from cross(G,C) is becomes bipartite, so original graph becomes planar
ie we could draw the cycle and then the missing edges inside and outside without any crossings
LEMMA: then nonplanar and subgraphs
Lemma If G is a subgraph of H, and G is nonplanar, then H is nonplanar.
Proof. To draw H, we’re drawing G and then adding some things
LEMMA:
Showing G isn’t planar:
Lemma If H is a subdivision of G and, and G isn’t planar, then H isn’t planar.
Proof. To draw H, we’re drawing G and then adding some dots on the edge
SUBDIVISION
A graph H is a subdivision of G if it can be created from G by adding some vertices of degree two in the middle of edges
Kuratowski’s theorem
proves a general G not planar
A graph G is not planar if and only if it has a subgraph that is a subdivision of K_{3,3} or K_5
EXAMPLE : planar?
\_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
using kuratowskis thm \_\_\_\_\_\_\_\_\_\_\_ | | [A]---[B]---[C] | | | / | | [D]--[E]---[F]----- | | / | [G]--[H]---[I]
degrees:
4,3,3,3,4,3,3,4,2
is a subdivision of graph K_{3,3} thus it isn’t planar
Kuratowski’s theorem proof:
A graph G is not planar if and only if it has a subgraph that is a subdivision of K_{3,3} or K_5
we don’t prove the only if direction:
if G is planar we can prove it by drawing it
we use that if G isn’t planar we know that we can find K_3,3 or K_5 in it
proof of if direction:
K_33 and k_5 aren’t planar
so subdivisions of them aren’t planar
(a subdivision of K_33 has 6 vertices of degree ≥ 3 at least
and of
K_5 have at least 5 vertices of degree ≥ 4)
so graphs having subdivisions
EXAMPLE:
[A]--[B]--[C] | | [D]--[E]--[F] | [G]--[H]
plus edges AF, and CH
This has degrees:
3,2,3,2,2,3,2,2
by colouring the vertices:
almost k_33
add edge CD then:
is a subdivision of K_33 so is not planar as original graph isn’t planar.
K4 isn’t planar, we prove this:
•—-•–¬
| / | |
•—-• |
|_____|
subdivide note:
if something isn’t planar we can use kuratowskis to show this always (IFF)
is the Petersen graph planar?
isn’t planar using kuratowskis thm.
No vertices of degree bigger than or equal to 4. So no subdivision of K_5- we don’t have enough vertices
colour vertex:
pick one vertex one colour and 3 neighbours other colour
*make top vertex orange, 3 adjacent purple.
*we need to make 2 more orange vertices and connect to all 3 purple vertices
*trial and error, orange is 2nd vertex on outside after top, third is RHS corner of inside star.
*we have coloured 3 orange and every 3 adjacent purple
SO it is a subdivision of k_3,3 as vertices of degree 3 and bipartite so not planar
kuratowskis thm note
is something isn’t planar adding extra edges isn’t going to make it planar
so we can fine a SUBGRAPH of G, and show that its a subdivision of K_5
=
Ie take away edges (vertices of the incorrect degree) from G to get a subgraph of it and to show that we can add edges to this subgraph to make K_5 or K_{3,3}
(a subdivision of K_33 has 6 vertices of degree ≥ 3 at least
and of
K_5 have at least 5 vertices of degree ≥ 4)
checking planar
*if Hamiltonian planarity algorithm:using given Hamiltonian cycle
crossing graph of vertices of edges not in HC
-crossing of graph redrawn cycle on outside and intersections between edges inside which didn’t appear in cycle
-Can number crossings to check
*if not necessarily HC exists/ not given use kurwatowskis:
IFF
A graph G is not planar if and only if it has a subgraph that is a subdivision of K_{3,3} or K_5
(ie we can add edges to a subgraph of these, we know its not planar, to get original graph which isn’t planar)
HINT:WE WILL USE BOTH IN EXAM
EXAMPLE: is G planar
given Hamiltonian CYCLE ABCDEFGA
METHOD 1
CROSSING GRAPH VERTICES
AF, GE,FC,DB,AC,EC,FD
FROM INTERSECTIONS OF INSIDE EDGES (CYCLE ON THE OUTSIDE)
from crossing graph:
5 cycle exists
BD-EC-FD-EG-FC-BD
(extra edges DB-CA and EG-AF)
because this 5 cycle exists then crossing graph isn’t bipartite so G isn’t planar
EXAMPLE: is G planar
METHOD 2
Need to find a subdivision of K_{3,3} or K_5
degrees:
4,3,4,4,4,5,3
5/7 vertices, all ≥ degree 4: so subdivision of k_5 exists
a subgraph of K_5 is by:
1)for the 5 edges of degree ≥ 4 try to draw K_5 to see which missing edges:
here we draw A,C,D,E,F and their edges to try and see K_5
2)adding edges -
G is missing AE and AD
This subgraph of G is a subdivision of K_5, so G isn’t planar
surface in R^3
“locally looks like” R^2
- Sphere S^2
- Torus T
- Mobius band M
*Klein bottle K
…
video game grid
video game map- locally a grid
cant get a sphere-cant model a sphere on a grid
Drawing graphs on the torus
Exam Question: “Draw G on the torus.
To draw a graph on the torus, draw it inside a square
If an edge hits a side of the square, it comes back at the same spot on opposite edge
*if it hits an edge it appears on the other side
to mark this is happening we
draw arrows:
| | or | |
↑ ↑ ↟↟
these edges glued together with this orientation(head to head, tail to tail)
we draw a square : -----↠------ | | ↑ ↑ | | -----↠-------
*edges going over the boundaty keep their order eg label
1 -| |
2-↑ -↑1
| -| 2
3-| -| 3
We cant draw K_5 in the plane:
Can we draw K5 on the torus?
1) draw a square around 5 vertices
2) connect the 5 vertices as cycle: consider which edges are missing and can draw those inside that don’t cross. OTHERWISE follow them out from middle
(don’t have to be straight) . If an edge hits a side it appears on the other side
label down and across the boundaries as the same order they cross them
diagram
**
example given in lectures slightly different from notes?
(im going to label ABCDE for reference)
draw 5 vertices, connect as cycle- draw out from all of them-number as order they cross the boundaries
(check degrees etc)
we have missing an edge CE and boundaries have differing numbers crossing so we correct this by drawing an arc from Left to bottom boundaries. (3 to 4)
if we follow our numbered edges to the vertices we see they form the missing edges from the middle of the K_5 graph
in total 6 pairs across boundaries
- different ways of drawing
- “5 edges missing but one got subdivided”
Can we draw K_6 on the torus?
*if we add a vertex to the inside of K_5 drawn on torus easily do this
Can we draw K_n on the torus?
*K_7 possible
and K_8 + aren’t possible
Not possible to draw
Kn for n≥8
on torus without edges crossing…
diagram: K6 in the notes from k5 IN THE NOTES version
what happens at the corner
we notice that each corner of the square comes out to next corner, so drawing one each from each vertex (2 to top left corner then 1 to each other corner from closest vertex)
all 4 corners of the square identify to 1 point
*useful to use a corner point as a vertex
consider the quadrants,
Mobius band:
Mobius band:
Like cylinder, but glued with a half twist
*a surface with only one side
WE SWAP THE BORDER ORDERS
EXAM QUESTION draw graph on mobius band
Can represent Mobius band in plane…
Can you draw K5 on the Mobius band?
Kn?
What happens when you cut a Mobius band in half?
Can represent Mobius band in plane…
rectangle with left and right hand side as boundaries
__________
↑ Down
__________
don’t cross top r bottom
WE SWAP THE DIRECTIONS ON MOBIUS BAND?? He didn’t in lectures until he cut in half but old notes say you do
Can you draw K5 on the Mobius band?
1)draw 5 vertices and connect in cycle
2)follow out edges to LEFT and RIGHT boundaries:
to connect the 5 edges we need
label 5 added crossing edges in order to check we have connected only the ones we were missing
Can you draw K6 on the Mobius band?
if we didn’t use the middle to draw k5 we can do k6 by adding a vertex in the middle
Can you draw K_7 on the Mobius band?
no we cant do k7 on the mobius band:
looking at our k5/k6 diagram we formed triangle shapes between edges (5 subdivided into 10) that we added
Using intuition we cant draw k7
What happens when you cut a Mobius band in half?
*stays in one loop: one strip with 2 full twists
\_\_\_\_\_\_\_\_\_\_\_\_ | x | ↑--------------------↑ | x | \_\_\_\_\_\_\_\_\_\_\_\_
one point in top with edge to boundary
and another in bottom half with other edge to boundary
= 2 points x although look different pieces boundaries connect
in plane-circles have inside and outside but not true for mobius strip and torus
K_{3,3} on Mobius band
write vertices in middle of mobius band in order of a Hamiltonian cycle in a line connected in a line with A connected to 3 by using the boundaries
we still need to connect A to 2,
B to 3 and 1 to C:
we can follow one edge from under A to Left boundary to 2
B to 3 under line by using the boundaries and 1 to c by avoiding boundaries and just connecting arc on top of line
\_\_\_\_\_\_\_\_\_\_\_\_ | | ↑ A 1 B 2 C 3 ↑ | | \_\_\_\_\_\_\_\_\_\_\_\_
label XYZ and check we’ve connected properly
K_{3,3} on a cut Mobius band
writing A 1 B in top half (connected with line through)
writing 2 C 3 in bottom half similarly
we connect above and below lines
remember that cut in half so label opposite? \_\_\_\_\_\_\_\_\_\_\_\_ |------A--1---B -----|Y ↑...….|….|…..|……..↑ |------2--C--3 -----|X \_\_\_\_\_\_\_\_\_\_\_\_ on LHS boundary order of labels is:
X| |Y
Y| |X
Draw K_{3,4} on the torus?
Tries drawing 4 boxes and 3 circles in cycle then trying to connect- we get stuck
- remember boundaries left and right and top,bottom continue in same order as crossing boundaries ie colour match or label
- another way alternating shapes in circle and square in the middle, 2 down one up, one curved from up to left then coming again from top right, and one on left middle to right middle
YES
* if i want to connect something in the bottom left to something in the top left i can: draw down from left to cross boundary as the left-most crossing, then draw this line down as left most crossing on the top boundary curving left to be the highest crossing on the left boundary. Then a line from the top right boundary comes out and we can connect
K_{3,4} on mobius band
similarly drawing in alternating squares and circles in circle-cycle, with square in the middle connected to each
Then colour coding to connect the other graphs
- see notes if stuck
- another way in lines
REMEMBER mobius band switches orders on left and right boundary (only boundaries) labels/colours
Theorem: Every football has 12 pentagons
as a corollary to Euler’s Theorem.
DEFINITION: Faces
Suppose that a graph G is drawn on the sphere S^2
so that no edges cross. Then G cuts the sphere into a finite number of pieces called the faces of G.
Vertices , Edges, faces of a cube
Vertices Corners
Edges Where two cube faces meet
Faces Faces of cube
Counting vertices, faces and edges
C_n
W_n
K_4
cube
Graph: V: E: F C_n :n :n: 2 Wn: n + 1: 2n: n + 1 K4 = Tetrahedra: 4: 6: 4 Cube: 8: 12: 6 Octahedron: 6: 12: 8 Dodecahedron: 20: 30: 12 Icosahedron: 12: 30: 20
DRAWN graph •-------• / \ / \ • • • \ / \ / •-------•
vertices=7
Edges =10
faces=5
(one face on bottom)
V+E=2+F
wheel graph
w_5
5 vertices, forming pentagon with spokes to the centre. This is a graph with n edges in cycle and n forming spokes so has 2n edges
cycle graph c_6
6 vertices in a hexagon shape: this has 2 faces
K_4
tetrahedron has 4 faces depending on how graph is drawn
THM: Euler formula
Euler’s formula for graphs on the sphere Let G be a graph drawn on the sphere without edges crossing. Let V and E be the number of edges and vertices of G, respectively, and let F be the number
of faces of the drawing. Then
V − E + F = 2
Euler
characteristic
V − E + F is called the Euler
characteristic
Using Eulers theorem
- handshaking relates edges and degrees
* handshaking between faces and edges
handshaking between faces and edges
Let the degree d(f ) of a face f be the number of edges around it.
*Then each edge meets two faces
* Each face f meets d(f) edges
SUM over faces of [d(f )] = 2E
graph on plane
If there is a graph on plane with n vertices m edges and p faces. then looks like theres a different planar graph with p vertices m edges and n faces
Deriving: handshaking between faces and edges
Adding an edge and adding faces?
degrees of faces
0
• one edge one face
•=• degree 2
triangle of 3 has degree 3
ie swap role of vertices and faces
definition of a football
Definition
A football, we mean a graph G drawn on the plane where:
*Every vertex v ∈ G has degree 3
* Every face f has degree 5 or 6
Suppose P pentagons and H hexagons so Faces is
proving football has 12 pentagons
faces F = P + H:
Eulers theorem:
V − E + P + H = 2
Vertex-edge Handshaking:
3V = 2E
For football: degree =3 for all and every face has degree 5 or degree 6
2E= sum over faces of degrees of faces = sum hexagons + sum pentagons = 6H + 5P -- 6V-6E+6P+6H=12 2E-5P-6H=0 6V+4E=0 ----------- give P=12
There have to be 12 pentagons but the number of vertices, edges and hexagons can vary
Use Eulers to prove K_5 isnt planar
Assume K_5 was planar and we drew it on the sphere with no edges crossing. Then by Eulers theorem:
V-E+F=2 5-10+F=2 F=7 SO any face has d(f) ≥3By face-edge handshaking. 2-= 2E= sum over faces of [d(F)] ≥ sum over f of [3] = 3(7)=21
contradiction as 20 is not bigger than 21
We can similarly prove that K_{3,3} isnt planar using Eulers thm
• ——•
| • |
| | |
• ——•
has 7 faces?
how do cycles affect faces?
*number of edges around a face affected
Kurwatowskis
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.
An edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices it used to connect
The following diagram illustrates this. First construct a subgraph of G by deleting the dashed edges (and the resulting isolated vertex), and then contract the gray edge (merging the two vertices it connects):
For example, the edge e, with endpoints {u,v}:
can be subdivided into two edges, e1 and e2, connecting to a new vertex w
note link:
https://personalpages.manchester.ac.uk/
staff/mark.muldoon/Teaching/
DiscreteMaths/LectureNotes/
PlanarGraphs.pdf
NOTE: eulers theorem for graphs on the sphere
We require the graph to be connected:
lets consider G not being connected :
6 vertices, 3 each form triangle so not connected graph
V=6 E=6 F=3
V-E+F=3 not equal to 2
(we have 3 faces
imagine on sphere:
st triangles cut out = discs and the face is a cylinder
*if you draw a graph on any surface S, so that all the faces are disks , then on other surfaces can get non-disk faces even with connected graphs
*if you calculate V-E+F = χ(S)
you always get the same # dep on S (surface) not on G nor on how its drawn
Proof of Euler’s theorem
*induction:
What happens if we delete an edge?
* Number of edges goes down by 1
* Number of faces goes down by 1?
Hence, V −E + F remains unchanged.
G a connected planar graph we want a process to get a simpler G that doesn’t change V-E+F
Example graph for Proof of Euler’s theorem
6 vertices connected: 2 triangles from 4 vertices ten 2 more on one side to make square off one triangle side
name edge e as the side a triangle and the square share
G: V=6
E=8
F=4
Let G’=G\e
Let V’,E’,F’ be the respective values for G’
We have:
V’=V (vertices stays the same)
E’=E-1 (deleted an edge)
F’= F-1 (merged 2 faces by deleting an edge)
New Euler characteristic is:
V’-E’+F’ = V -E+1+F+1 = V-E-F
*basic idea works for any face, but have to be careful as if we delete the ‘;wrong’ edge we might disconnect G.
If G drawn on sphere and has one face, Then G is a tree Equivalent to
G isn’t a tree, then it has more than one face
G is connected so if G is not a tree it has a cycle . But then that cycle has inside and outside
Proof of Eulers : First proof
Base case: G has only one face
- Then G has no cycles (Jordan curve theorem)
- Assumed G connected, so it’s a tree
- Therefore E = V−1
Inductive step:
Assume G has F > 1 faces and theorem is true for all graphs with fewer than F faces.
Then G has an edge separating two faces
Deleting such an e doesn’t disconnected G :
we need to find an edge e that doesn’t disconnect graph so that we can delete e. Deleting e doesn’t disconnect G because we can go around the “other side” of f_1 or f_n
Take a path from a point in f to one in f’- this has to cross into another face at some point
G {e} has one less face, so theorem holds there
Back to videogames
Recall that the standard overhead view of a planet in video game produces not the sphere but the torus.
DEFINITION:
A video game graph
A video game graph is a graph drawn on a surface so that
- Every vertex has degree 4
- Every face has degree 4
- locally looks like a grid so degrees of 4 arise
THM video gram graph
A video-game graph can never be the sphere. In fact, a video-game graph will always be the torus or the Klein bottle.
PROOF
THM
A video-game graph can never be the sphere. In fact, a video-game graph will always be the torus or the Klein bottle.
1) Euler's theorem Suppose that G was a video game graph drawn on the sphere: V −E + F = 2 2) Vertex-edge handshaking Since every vertex has degree 4, we have 2E = 4V
3) vertex-face handshaking
Since every face has degree 4, we have
2E = 4F
E=2V and 2F=E=2V gives
F=V
- sphere is supposed to have V-E+F=2 but here we have V-E+F has to be 0 so contradiction on the sphere
- torus=0
Duality
cube and octahedron
\_\_\_\_\_\_\_\_ | \\_\_\_\_\_\_/ | | | | | | |_ \_\_\_\_| | | /\_\_\_\_\_\_\ |
The cube has (V,E,F) = (8,12,6) I The octahedron has (V,E,F) = (6,12,8)
see notes for diagram:
(circle around inner border, vertex in middle with vertical and horizontal to border, horizontal down and around outside, one loop from left horizontal to top of vertical)
vertex in middle for each face and edges perpendicular
- for every edge look at two faces it separates and connect them: for every edge get edge, for every face get a vertex.
- at each vertex of cube missing 90 degrees = pi/2 radians and 8 vertices.
so in total missin g 8(pi/2) = 2 (2 pi) = 2 full circles
Eulers theorem tells us that no matter how we cut the sphere up into polygons, always be missing 2 full circles of points
Definition: duality/dual graph
Let G be a planar connected graph. The dual graph G∗ of G has:
- One vertex for each face of G, placed in the middle
- One edge for each edge of G, drawn perpendicular
- One face for each vertex of G
Note du
Explains the pattern we saw in V,E,F
Face-edge handshaking for G is vertex-edge handshaking for G∗, and vice versa.
THE DEGREE OF A FACE
is at least 3- for simple graphs must be at least 3
