← Graphs and Networks › Graph Theory — Definitions and Representations

Graph Theory — Definitions and Representations

Key Terms

A graph consists of vertices (nodes) connected by edges (arcs); The degree of a vertex = number of edges meeting at that vertex (a loop counts as 2)
Walk: any sequence of vertices and edges (edges/vertices may repeat)
Trail: a walk where no edge is repeated
Path: a walk where no vertex is repeated
Cycle: a closed path (starts and ends at same vertex, no repeats); A graph is connected if there is a path between every pair of vertices
Weighted graph: each edge has a numerical value (distance, cost, time)
Directed graph (digraph): edges have a direction (one-way); Handshaking lemma: sum of all degrees = 2 × number of edges

Degree sum formula (Handshaking Lemma):
Σ deg(v) = 2 × |E|
(sum of all vertex degrees = twice the number of edges)

Complete graph K_n: every vertex connected to every other; has n(n−1)/2 edges

Tree: connected graph with no cycles; has exactly n−1 edges for n vertices

Worked Example: A graph has vertices A, B, C, D, E with edges: AB, AC, BC, BD, CD, DE.

Degree of each vertex: deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 1
Sum of degrees = 2 + 3 + 3 + 3 + 1 = 12 = 2 × 6 edges ✓
Vertices with odd degree: B, C, D, E (4 vertices)
The graph is connected (you can reach any vertex from any other).

Hot Tip: The number of vertices with odd degree is always even (a consequence of the Handshaking Lemma). This fact is the key to determining whether Euler trails and circuits exist.

What Is a Graph?

In mathematics, a graph is a set of points (vertices) connected by lines (edges). Graphs are used to model real-world networks: roads, computer networks, flight routes, social connections, and more.

Key Definitions

Vertex (pl. vertices): a point in the graph, often labelled with a letter or number
Edge: a line connecting two vertices (or a vertex to itself — a loop)
Degree: the number of edges meeting at a vertex (loops contribute 2)
Simple graph: no loops and no multiple edges between the same pair of vertices
Weighted graph: each edge has a numerical weight (e.g. distance in km)
Directed graph (digraph): each edge has an arrow indicating direction

Walks, Trails, Paths, and Cycles

These terms describe how you move through a graph:

Walk: any sequence of vertices connected by edges — you can repeat edges and vertices
Trail: a walk that uses each edge at most once (but may revisit vertices)
Path: a walk that visits each vertex at most once (no repeats at all)
Cycle: a closed path — starts and ends at the same vertex with no other repeats

Representing Graphs

Graphs can be represented as:

Diagrams: the visual representation
Edge list: list all edges, e.g. {AB, BC, CD, DA}
Adjacency matrix: a grid where entry (i,j) = 1 if vertices i and j are connected (or the weight of the edge)

Strategy: When answering graph theory questions, first identify: How many vertices? How many edges? What is the degree of each vertex? Is the graph connected? These four facts answer most basic questions.

Mastery Practice

See Answers ➔

Fluency A graph has vertices A, B, C, D with edges AB, AB, BC, CD, DA (note: two edges between A and B). State: (a) the number of vertices (b) the number of edges (c) the degree of each vertex.
Fluency A graph has 5 vertices with degrees 1, 2, 3, 4, 4. Verify the Handshaking Lemma by finding the number of edges.
Fluency State whether each sequence describes a walk, trail, path, cycle, or none of the above, for the graph with edges AB, BC, CD, DA, AC:
- (a) A → B → C → A
- (b) A → B → C → D → A
- (c) A → C → B → A → D
Fluency A complete graph K₄ has 4 vertices, each connected to every other. How many edges does it have? What is the degree of each vertex?
Understanding A graph has 6 vertices: P, Q, R, S, T, U with edges PQ, PR, QR, QS, RT, ST, TU, SU. Draw the adjacency matrix for this graph and find the degree of each vertex.
Understanding A connected graph has 7 vertices and is a tree. How many edges does it have? Justify your answer.
Understanding The following adjacency matrix represents a graph. List all edges and find the degree of each vertex.

A B C D

A 0 1 1 0

B 1 0 1 1

C 1 1 0 1

D 0 1 1 0
Understanding A network of roads connects towns A, B, C, D, E. The roads are: A–B (12 km), A–C (8 km), B–C (5 km), B–D (10 km), C–E (15 km), D–E (6 km). This is a weighted graph. (a) How many edges? (b) Which town has the highest degree? (c) Is the graph connected?
Problem Solving A simple graph has 5 vertices. The degrees of four of the vertices are 1, 2, 3, and 4. What must the degree of the fifth vertex be? Is more than one value possible?
Problem Solving A graph has vertices A, B, C, D, E, F. Every vertex has degree 3 (this is called a cubic or 3-regular graph).
- (a) How many edges does this graph have?
- (b) Is it possible for a simple graph with 5 vertices to be 3-regular? Explain why or why not.
- (c) Construct an edge list for one possible 3-regular graph on 6 vertices.

	A	B	C	D
A	0	1	1	0
B	1	0	1	1
C	1	1	0	1
D	0	1	1	0

View Full Worked Solutions →