A comprehensive package of PowerPoint presentations and accompanying worksheets designed to introduce the captivating world of graph theory to high school students studying VCE Specialist Mathematics.

• vertices and edges for undirected graphs, including multiple edges and loops, and their representation using lists, diagrams and adjacency matrices
• examples of graphs from a range of contexts such as molecular structure, electrical circuits, social networks, utility connections and their use to discuss types of problems in graph theory including existence problems, construction problems, counting problems and optimisation problems
• the degree of a vertex and the result that the sum of all the vertex degrees is equal to twice the number of edges (the handshaking lemma)
• simple graphs, isomorphism, subgraphs, connectedness, complete graphs and the complement of a graph
• bi-partite graphs, trees, and regular graphs (including the Platonic graphs)
• planar graphs and related proofs and applications such as:

-Euler’s formula v+f-e=2 for simple connected planar graphs

-the complete graph K_n on n vertices has (n(n-1))/2 edges

–a regular graph with n vertices each of degree r has nr/2 edges

-the planarity of various types of graphs, including all trees, complete graph on n vertices, if n≤4, and K_(m,n), the complete bipartite graph with m,n  vertices, if m≤2 or n≤2

• equivalent conditions for a simple graph with 𝑛 vertices to be a tree
• trails and circuits, Euler circuits and Euler trails, Hamiltonian cycles and paths, and the Konigsberg bridge problem.