MAT3707 Graph Theory – University of South Africa – Summary of Formulae for Chapter 1 (Study Units 1–6)

Contents
Part 1 – Graph Theory (Study Units 1–6) .......................................................................................................2
1. Introduction to Graphs .................................................................................................................................2
2. Planar Graphs ...................................................................................................................................................3
3. Euler Cycles & Hamilton Circuits ..............................................................................................................4
4. Graph Colouring...............................................................................................................................................5
5. Trees .....................................................................................................................................................................6
6. Minimal Spanning Trees...............................................................................................................................6

, Part 1 – Graph Theory (Study Units 1–6)

1. Introduction to Graphs
Key Definitions:

• Graph: finite set of vertices 𝑉 and edges 𝐸 joining pairs of distinct vertices (no
loops/parallel edges).

• Vertex (node); Edge (link); Adjacent vertices; Incident edge; Order 𝑛 = |𝑉|;

Size 𝒆 = |𝑬|.

• Directed graph (digraph) – edges have direction; in-degree, out-degree.

• Path – sequence of distinct vertices/edges; Length = number of edges.

• Circuit – path returning to start vertex.

• Connected graph – path between every pair of vertices.

• Component – maximal connected subgraph.

• Degree 𝑑(𝑣) – number of neighbours; Isolated vertex – degree 0.

• Isomorphic graphs – same adjacency structure.

• Complete graph 𝐾𝑛 – all vertices adjacent.

• Bipartite graph – vertex set split into two independent sets;

Complete bipartite graph 𝐾𝑚,𝑛

• Complement – edges between all non-adjacent pairs.

• Subgraph – subset of vertices/edges.

Theorems:

• Edge-counting theorem: ∑𝑣∈𝑉 𝑑(𝑣) = 2𝑒 (undirected graphs). Proof uses each
edge contributing degree 2.

• Characterisation of bipartite graphs: A graph is bipartite ⇔ no odd-length
circuits.