Introduction to Graph Theory: Basic Definitions

A graph G = (V, E) consists of a set V of vertices and a set E of edges, each edge joining two vertices; the degree of a vertex is the number of edges at it, and the handshake lemma states that the degrees add up to twice the number of edges. In brief: the graph with the vertices A, B, C, D and the edges AB, AC, BC, CD has the degrees 2, 2, 3, 1, whose sum 8 equals 2 · 4 edges. Because the degree sum is always even, no group of 7 people can each shake hands with exactly 3 others.

Graphs model networks of any kind: roads, friendships, computers, molecules. This guide introduces the basic vocabulary (vertices, edges, degree, walks, paths, cycles, connectivity), the main kinds of graphs (simple, directed, weighted, complete), the adjacency matrix and graph isomorphism, with worked examples and a table of terms.

What is a graph?

A simple graph has a finite set of vertices (nodes) V and a set of edges E, each edge being an unordered pair of distinct vertices. Two vertices joined by an edge are adjacent, and the edge is incident to its endpoints. The number of vertices |V| is the order of the graph and |E| its size. A drawing is only a picture: what matters is which vertices are joined, not where they are placed or whether the edges are straight.

Example 1: reading a graph

For the graph in the figure, V = {A, B, C, D} and E = {AB, AC, BC, CD}. A and B are adjacent; A and D are not. The triangle ABC is a part of the graph.

What are degrees and the handshake lemma?

The degree deg(v) is the number of edges incident to v. Every edge has two ends, so Σ deg(v) = 2|E| (the handshake lemma). Consequently the number of vertices of odd degree is even.

Example 2: degrees

In the figure, deg A = 2, deg B = 2, deg C = 3, deg D = 1, and the sum is 8 = 2 · 4 ✓. The vertices of odd degree, C and D, are two in number.

Example 3: an impossible party

Can 7 people each shake hands with exactly 3 others? The degree sum would be 21, which is odd, so no. With 8 people it is possible (for instance on the cube graph, 12 handshakes).

Example 4: a degree sequence

Is there a simple graph with the degrees 3, 3, 2, 2, 1, 1? The sum is 12, so the graph would have 6 edges, which is not forbidden by parity. One construction: the vertices a, b with degree 3 joined to each other, a joined to c and d, b joined to c and e, and d joined to f. Then deg a = 3 (b, c, d), deg b = 3 (a, c, e), deg c = 2, deg d = 2 (a, f), deg e = 1, deg f = 1 ✓.

What are walks, paths and cycles?

A walk is a sequence of vertices in which consecutive ones are adjacent; its length is the number of edges. A trail does not repeat edges, and a path does not repeat vertices. A closed walk returns to its start, and a cycle is a closed path of length at least 3. A graph is connected if any two vertices are joined by a path; otherwise it splits into connected components. The distance between two vertices is the length of a shortest path.

Example 5: paths in the figure

A–C–D is a path of length 2, so the distance between A and D is 2. A–B–C–A is a cycle of length 3. The walk A–C–B–C–D repeats the vertex C, so it is a walk and not a path. The graph is connected.

What kinds of graphs exist?

• Multigraphs allow parallel edges, and pseudographs allow loops.
• Directed graphs (digraphs) have edges with a direction, written as arrows; the degree splits into the in-degree and the out-degree.
• Weighted graphs attach a number (a distance, a cost) to each edge.
• The complete graph K_n has all possible edges, n(n − 1)/2 of them.
• A subgraph uses some of the vertices and edges of another graph; the complement of G has the same vertices and exactly the edges that G lacks.

Example 6: counting edges of K_n

K₅ has 5 · 4/2 = 10 edges, each vertex has the degree 4, and the degree sum is 20 = 2 · 10 ✓. The complement of the graph in the figure has the 6 − 4 = 2 edges AD and BD.

Example 7: isomorphism

Two graphs are isomorphic if a bijection between their vertices preserves adjacency; they are then the same graph drawn differently. Necessary conditions are equal orders, sizes and degree sequences. A path with 4 vertices (degrees 1, 2, 2, 1) and the figure graph (degrees 2, 2, 3, 1) are not isomorphic: their degree sequences differ.

How do you represent a graph by a matrix?

The adjacency matrix A has a_ij = 1 if vertices i and j are adjacent and 0 otherwise. For an undirected simple graph it is symmetric with zeros on the diagonal, and the row sums are the degrees. The entry (i, j) of A^k counts the walks of length k from i to j.

Example 8: the adjacency matrix and walks

For the figure with the order A, B, C, D: A = [[0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]]. The row sums 2, 2, 3, 1 are the degrees. In A², the entry (A, D) is 1 · 0 + 1 · 0 + 1 · 1 + 0 = 1: exactly one walk of length 2 from A to D (through C). The diagonal entries of A² are the degrees, and tr(A³) equals six times the number of triangles: here 6 · 1 = 6.

Table of terms

Where does graph theory come from?

Graph theory began in 1736, when Leonhard Euler solved the problem of the seven bridges of Königsberg. The word “graph” in this sense was introduced by James Joseph Sylvester in 1878, and the first textbook was written by Dénes Kőnig in 1936. The handshake lemma is also due to Euler. Modern applications range from the internet to social networks and chemistry.

Which mistakes are common?

Confusing a graph with its drawing

Crossings and positions are irrelevant. Two very different pictures can show the same graph.

Mixing up path, trail and walk

A path repeats no vertex, a trail repeats no edge, and a walk may repeat both.

Counting edges of K_n as n²

Each edge joins an unordered pair, so K_n has n(n − 1)/2 edges.

Forgetting loops in the degree

In graphs with loops, a loop contributes 2 to the degree of its vertex.