Sample learning activity – graph theory constructions and proofs

Specialist Mathematics Unit 1

Sample learning activity – graph theory constructions and proofs

Introduction

The module on the Australian Mathematical Sciences page provides an excellent introduction to the beginning student of graph theory:

http://amsi.org.au/ESA_Senior_Years/SeniorTopic7/7_md/SeniorTopic7a.html

The following collections of related results can be proved after the initial exploration of ideas using a collection of sample graphs constructed by hand and/or using technology, for example: http://illuminations.nctm.org/Activity.aspx?id=3550 or https://visualgo.net/en/mst

Part 1

Prove that the sum of the degrees of the vertices of any finite graph is even.

a.  Show that every simple graph has two vertices of the same degree.

b.  Show that if n people attend a party and some shake hands with others (but not with themselves) then at the end, there are at least two people who have shaken hands with the same number of people.

c.  Prove that a complete graph with n vertices contains edges.

d.  Prove that a finite graph is bipartite if and only if it contains no cycles of odd length.

Part 2

a.  Show that any graph where the degree of every vertex is even has an Eulerian cycle. Show that if there are exactly two vertices of odd degree, there is an Eulerian path from one to the other.

b.  Show that if there are more than two vertices of odd degree, it is impossible to construct an Eulerian path.

c.  Show that in a directed graph where every vertex has the same number of incoming as outgoing paths there exists an Eulerian path for the graph.

Areas of study

The following content from the areas of study is addressed through this learning activity.

Area of study / Topic(s) / Content dot point
Discrete mathematics / Graph theory / 1, 2, 3, 4, 5, 6

Outcomes

The following outcomes, key knowledge and key skills are addressed through this task.

Outcome / Key knowledge dot point / Key skill dot point
1 / 1, 2, 3, 4 / 1, 2, 3, 4
2 / 2, 3, 4 / 2, 3, 4
3 / 1, 3 / 1, 4, 5, 9, 10

© VCAA Page 2