Faculty of Mathematics Centre for Education in

Waterloo, Ontario N2L 3G1 Mathematics and Computing

Grade 6 Math Circles

February 18/19, 2014
Graph Theory II- Solutions
* indicates challenge question

1. Are the following graphs planar? If so, draw a planar representation. If not, explain
why. Hint: Only one of these are planar. Try finding K5 or K3,3 subdivisions.
(a) Planar, drawing may vary (b) Non-planar: K5 subdivision
1 1
6
6 2
12
7 8 5 2

7
5
11 9
3 9 8
4 3
4
10

(c) Non-planar: K3,3 subdivision (d) Non-planar: K5 subdivision

a
a
c d b

e b

f
g c
f
e g
h h d

1
2. Redraw each graph to show it is planar.

(a) Drawing may vary. (b) Drawing may vary.

6
a b c
2 4
1

d e f
7 5
9
g
h i
3 8

3. There are five teams in a tournament.

(a) Use a graph to prove that there is a way for each team to play every other team
once.
1

i. How many games does each team play?

5 2
Each team plays 4 games

ii. What is the total number of games played?

4 3 There are 10 games played.
K5
(b) The organizers of the tournament would like to consider the different number of
games each team can play (ie. how many games each team should play). Assuming
each team must play at least one game, the options are for each team to play 1
game, 2 games, 3 games, or 4 games. Assume that each team has to play the
same number of games, and that teams cant play each other more than once.
i. Is it possible to draw a graph for all the different number of games? Explain.
Be sure to use specific reasons you learnt in this lesson.
1 and 3 are not possible. If there is an odd number of teams and each team
plays an odd number of games, then the sum of the degrees will be an odd
number. But the Handshake Lemma says that the number of edges is half of
the sum of the degrees. Since the sum is odd, then the number of edges will
not be a whole number. But we know this can not be true. For example, if
each team played 1 game, the sum of the degrees will be 5. By the Handshake
Lemma there should be 2.5 edges. However, we can not have half an edge.

2
 ii. Draw one graph for each number of games that is possible.
The graph for 4 games is drawn in part (a). This is the graph for 2 games
(note that it may be drawn in different ways, but each vertex must have two
edges connected to it):
1

5 2

4 3

iii. Can you fix the scenarios from part i) by removing one of the assumptions?
You must still assume that each team has to play at least one game. Answers
may vary. Example: adding an extra game.

4. *How can you rearrange vertices to make it easier to see the minimum colouring. (Hint:
think about grouping vertices according to what they are connected to) Answers may
vary. You can group together vertices that are not adjacent, then make each group
one colour

5. Find the minimum colouring for each of the following graphs. A good strategy for these
questions is to colour one vertex, and assign a different colour to adjacent vertices
by trying to use colours that have already been used and adding new colours when
necessary.
(b) 3-colouring as shown
(a) 2-colouring as shown

3
 (c) 5-colouring as shown
(d)

K8
Remember that K8 means that there are 8 vertices and
each vertex is connected to the 7 other vertices. Since all
the vertices are connected to each other, no two vertices
can have the same colour. Therefore, it is an 8-colouring
as shown.
6. Draw a graph that is 1-colourable, 5-colourable, 10-colourable, 20-colourable, 50-
colourable, 100-colourable, and 1000-colourable. Answers may vary. There can be
more than 1 vertex, but since the graph must be 1-colourable none of the vertices can
be connected. A sample answer is a single vertex.

7. Draw a graph that has a minimum colouring of (The easiest graph would be the
complete graph (Kn ) where n represents the minimum colouring needed)

(a) 1

(b) 3

(c) 5
(d) *10

4
8. A word graph has words as the vertices. Two words are adjacent if they differ by 1
letter. Create a connected word graph that contains the following words: log, top, eat,
mud and rag. Answers may vary.
rag.
mud.

mug.
rug.
eat.

pat. tug. bug.

pot. tag.
bog.
pop.
tap.

top. log.

9. Eulers Oil is a gas station chain in the country of Mathisfun. The CEO of the company,
Leonhard, wants to visit all his gas stations in the country to ensure that each one is
stocked with enough fuel. However, he doesnt want to visit any town more than once
as he is a very busy man. Suggest a route Leonhard could take from the head office in
the capital Mathtopia, through each town exactly once, and return to the capital. Note
that despite the intersection of three highways in the centre of the country, there is no
way to change from one road to another (i.e. there is no direct road from Mathtopia
to Gausston, etc.) Answers may vary. One solution is Mathtopia, Circle City, Fraction
Falls, Radius River, Times Town, Equationville, Gausston, Vertex Village, Mathtopia
Vertex Village

Times Town Gausston

Radius River
Equationville
Mathtopia

Circle City
Fraction Falls

5
10. Below is a map of South America. Create a graph with the vertices representing coun-
tries and the edges joining those countries which share a land border. So Chile and
Peru are adjacent, but Peru and Uruguay are not. Use your graph to answer the ques-
tions below.
Venezuela
Guyana
Suriname
Columbia
French Guiana

Ecuador
Brazil
Peru
Bolivia

Chile Paraguay
Uruguay

Argentina
Courtesy of abcteach.com

(a) Find the minimum colouring of the graph, and determine a colour for each country.
Watch out for countries that that share a very small border. Since borders do
not cross, there must be a way to draw a planar graph of the map. The 4-colour
theorem says that any planar graph is 4-colourable. Although it is possible that
a planar graph is less than 4-colourable, there is a subgraph (meaning a smaller
graph within the original) of K4 (consisting of Brazil, Bolivia, Paraguay, and
Argentina). Remember that K4 denotes the complete graph with 4 vertices that
are all adjacent to each other, which requires at least 4 colours.
(b) When trading goods over land, a $100 tax is paid to each country which the goods
travel through. So if Columbia sells coffee to Venezuela, the least amount of tax
paid is $100.
i. What is the least amount of tax paid on wool shipped from Ecuador to
Paraguay? $300
ii. What country can trade with the most others for exactly $100? Brazil
iii. Brazil raises its taxes to $400. What is the cheapest amount of taxes paid
to ship Venezuelan oil to Paraguay? What about French Guiana to Bolivia?
Venezuela to Paraguay: $400; French Guiana to Bolivia: $500
iv. To encourage trade, Peru will not tax any goods going though the country.
Chile and Suriname want to trade lumber and wheat. What route will result
in the least amount of taxes? How much will they pay? Suriname, Guyana,
Venezuela, Columbia, Peru, Chile; $400

6
 (c) Kevin wants to visit every country in South America on his vacation. He doesnt
want to visit any country more than once since crossing the border can take a
long time! He will fly into Lima, Peru to begin his trip and fly out of Montevideo,
Uruguay. In what order should he visit each country? Peru, Ecuador, Columbia,
Venezuela, Guyana, Suriname, French Guiana, Brazil, Paraguay, Bolivia, Chile,
Argentina, Uruguay

11. *Two graphs are isomorphic if they are the same graph drawn in a different way. This
means that all the connections are the same, and there are exactly the same number of
vertices, but the vertices may have different names and the graphs may look different.
Determine if the following pairs of graphs are isomorphic. If so, show which vertices
match, or explain why not.

(a) Not isomorphic: there is a cycle of length 3 in the first, but not in the second.
1 a
6 2 f b

5 3 e c

4 d

(b) Isomorphic as shown (solutions may vary)

1 2 3 4 e a b f

5 6 7 8 g c d h

(c) Isomorphic as shown (solutions may vary)

1 a

5 6 2 i j
8 e b
9 f
10 7 g d

4 3 h c

12. *Use planarity (including the theorems) to colour the planar graphs from question 1.
Since question (a) is planar, it must be four-colourable by the theorem (students may

7
 also realise that it is 3-colourable).

13. ***Prove the six-colour theorem. The following is a simplified version of an inductive
proof. Induction is a proof method that starts with the simplest base case, and builds
up to show it is true for any number. Think of induction as a prince trying to climb
a ladder to get to his princess who is at the top of a castle. You want to prove that
he can get onto the first step of the ladder. Then you can prove he can make it to the
second, then the third, and so on. With mathematical induction, instead of proving
that he can make it to a specific step we prove the first step and show that it works for
a generalized step (usually represented with a variable). True induction is quite hard,
so it is acceptable at this level to show the general idea.
We start with 1 vertex. This is 6-colourable since we only need one colour. The same
idea can be used for all planar graphs with 6 or less vertices.
Next, we look at a graph with 7 vertices. From the theorem presented in the lesson,
there must be a vertex with degree 5 or less. If we temporarily remove this vertex, we
have a graph with 6 vertices. We have already proven that a graph with 6 vertices is
6-colourable, so we can colour this graph. Adding the 7th vertex back, we can use the
colour of the vertex that it is not connected with to colour it. Since we have only used
6-colours, this graph with 7 vertices is 6-colourable.
Using the same idea, we can start with 8 vertices and remove a vertex with degree 5
or less. Then we have a graph with 7 vertices. We have proven this is 6-colourable, so
adding the 8th vertex back in, we can colour it by using one of the colour(s) that is
not taken up by an adjacent vertex.
Using this idea in general (this is the hard part), we have proven the base case, so we
assume that the 6-colour theorem is true for k 1 vertices. Looking at a graph with k
vertices, we can remove the vertex with degree 5 or less so we have k 1 vertices left.
Since we assumed this is true, we can add the remaining vertex and colour it with the
remaining colour.