MA010 Tutorial 6
Fr´ed´eric Dupuis
This tutorial covers material from lecture 7 (planarity).
Problem 1
Are these graphs planar or not? If they are planar, give a planar drawing, if not, prove
that they are not (possibly by using Kuratowski’s theorem...)
paq pbq
Sources: www.math.uwaterloo.ca/˜dgwagner/CO220/co220sols6.pdf,
www.math.hawaii.edu/˜marriott/teaching/summer2010/math100/planar_graphs_homework.
pdf
Problem 2
Of the following three isomorphic planar graphs, which ones are equivalent drawings
and which are not? Why?
paq pbq pcq
1
Problem 3
Show that a connected planar bipartite graph with n ě 3 vertices can have at most e ď
2n ´ 4 edges. Show that this is the best possible bound by giving a bipartite planar graph
where this equality is attained.
Source: www3.nd.edu/˜dgalvin1/40210/40210_S12/40210S12-E1_sols.pdf
Problem 4
Call a graph “outer planar” if it can be drawn on the plane with no crossings such that
all vertices are on the outer face. Show that every outer planar graph is 3-colourable.
Source: wetalldid.com/study/maryland/jhu/math_550.472_graph_theory/amitabh_basu/
math_550.472_graph_theory_homework_10_amitabh_basu_sp2014.pdf
Problem 5
Show that a simple, 2-connected, 6-regular planar graph cannot exist. (Recall that 6regular
means that every vertex has degree 6.)
Hint: How many faces can there be compared to the number of edges? Now try counting the
number of faces a second way...
2