Home / Courses / Discrete Mathematics / Unit 8

Discrete Mathematics Unit 8: Graph theory

Graphs model connections: networks, maps, schedules. Vertices are the objects and edges are the links.

Covers: Graphs, paths & circuits (Euler, Hamilton), trees, coloring, planarity

Study guide

A graph is a set of vertices connected by edges. Graphs can be directed or undirected, simple or with multiple edges and loops. The degree of a vertex is its number of edges, and the handshake lemma says the sum of all degrees equals twice the number of edges, so the number of odd-degree vertices is even. Special graphs include complete graphs Kₙ, cycles, and bipartite graphs, whose vertices split into two sets with edges only between them.

A path is a sequence of edges between vertices, and a circuit returns to its start. A graph is connected if every pair of vertices has a path between them. An Euler path uses every edge exactly once; a connected graph has an Euler circuit exactly when every vertex has even degree, and an Euler path exactly when zero or two vertices have odd degree. A Hamilton path visits every vertex exactly once; no simple test exists for Hamilton circuits.

A tree is a connected graph with no cycles. A tree with n vertices has exactly n − 1 edges, and there's a unique path between any two vertices. Spanning trees connect all vertices of a graph, and minimum spanning trees (found by Kruskal's or Prim's algorithm) minimize total edge weight.

Graph coloring assigns colors so adjacent vertices differ; the chromatic number is the fewest colors needed. A planar graph can be drawn without edge crossings. Euler's formula for connected planar graphs is V − E + F = 2, and every planar graph can be colored with four colors.

The distance between two vertices is the number of edges on a shortest path between them. A connected graph's diameter is the largest distance between any pair of vertices. A graph is bipartite exactly when it is 2-colorable, which is exactly when it has no cycle of odd length. So finding one odd cycle proves the chromatic number is at least 3.

Kruskal's algorithm sorts the edges by weight and repeatedly adds the lightest edge that doesn't create a cycle. Prim's algorithm starts from one vertex and repeatedly adds the lightest edge joining the tree to a new vertex. Both stop with n − 1 edges and give a minimum spanning tree. A forest (a graph with no cycles) with n vertices and k connected components has exactly n − k edges. A graph with n vertices, m edges and k components therefore has at least m − n + k independent cycles. Removing an edge that lies on a cycle doesn't change the number of components.

Graph proofs often use induction on vertices or edges: remove a vertex of small degree, apply the hypothesis to the smaller graph, then put the vertex back. Another common tool is to consider a longest path. For example, if every vertex of a finite directed graph has an outgoing edge, the last vertex of a longest path must point back into the path, creating a cycle.

Key ideas

• Handshake lemma: the sum of degrees is twice the number of edges.
• Euler circuit (every edge once): exists in a connected graph iff every vertex has even degree.
• Hamilton circuits visit every vertex once; there's no simple test.
• A tree is connected with no cycles; n vertices means n − 1 edges.
• Planar graphs satisfy Euler's formula; graph coloring assigns colors so neighbors differ.

Formulas and rules

Common mistakes

• Mixing up Euler (edges) and Hamilton (vertices) circuits.
• Forgetting a graph must be connected for an Euler circuit.

Words to know

Handshake lemma

The sum of all vertex degrees equals 2 × the number of edges.

Euler circuit

Exists in a connected graph when every vertex has even degree.

Edges in a tree with n vertices

n − 1

Euler's formula for planar graphs

V − E + F = 2

Euler circuit vs Hamilton circuit

Euler uses every edge once; Hamilton visits every vertex once.

Graph

Vertices connected by edges.

Degree of a vertex

The number of edges at it.

Complete graph (Kₙ)

Every pair of vertices is connected.

Bipartite graph

Vertices split into two sets with edges only between them.

Connected graph

A path exists between every pair of vertices.

Euler path

Exists when exactly zero or two vertices have odd degree.

Hamilton path

Visits every vertex exactly once.

Spanning tree

A tree containing every vertex of the graph.

Chromatic number

The fewest colors needed so adjacent vertices differ.

Four color theorem

Every planar graph can be colored with four colors.

Tree (graph theory)

A connected graph with no cycles; one path between any two vertices.

Sample practice questions

21 more questions like these, from level 1 to 5, are in the practice set.