Discrete Math › Section C · Graph theory › Topic C.1

What is a graph?

Road maps, friendship networks, computer networks and molecules all share one shape: things, and connections between pairs of them. A graph captures exactly that shape, and nothing else, which is why one theory can answer questions about all of them at once.

Dots and connections

A graph \(G = (V, E)\) consists of a set \(V\) of vertices and a set \(E\) of edges, where each edge is a pair of distinct vertices. In a city map the vertices might be junctions and the edges the streets between them; in a social network the vertices are people and the edges are friendships. A drawing is only a picture of the graph. Moving the dots around, or bending the lines, gives the same graph, because the graph records only which pairs are joined. Lengths, angles and positions mean nothing unless we add them deliberately.

The basic vocabulary

Two vertices are adjacent when an edge joins them, and that edge is incident to both. The neighbours of a vertex are the vertices adjacent to it, and its degree, written \(\deg(v)\), is the number of edges incident to it. Unless we say otherwise, graphs here are simple: no edge from a vertex to itself (a loop) and at most one edge between any two vertices. A multigraph allows loops and repeated edges; a loop adds 2 to the degree of its vertex. A directed graph gives every edge a direction, like a one-way street, but this section mostly uses undirected graphs.

The handshake lemma

Add up the degrees of all the vertices. Every edge has two ends, so every edge is counted exactly twice:

\sum_{v \in V} \deg(v) = 2|E|

Picture a party where an edge is a handshake between two guests. Each handshake involves two hands, so the total number of hands shaken is twice the number of handshakes. One consequence follows at once. The degree sum is even, so the vertices of odd degree must come in an even number: no graph has exactly one, three or five vertices of odd degree.

Worked example: which degree lists can exist?

1. Degrees 3, 3, 2, 2, 2: the sum is 12, so a graph would have 6 edges. One exists. Take vertices \(a, b, c, d, e\) with edges \(ab, ac, ad, bc, be, de\); then \(a\) and \(b\) have degree 3 and the rest have degree 2. 2. Degrees 4, 3, 3, 3, 2: the sum is 15, which is odd, so no graph has these degrees. 3. Seven people, each shaking exactly three hands: the sum would be 21, also odd, so this is impossible. 4. Degrees 3, 3, 0, 0 sum to 6, yet fail: in a simple graph on 4 vertices, degree 3 means being adjacent to every other vertex, including the ones of degree 0. An even sum is necessary, not sufficient.

Walks, trails, paths and cycles

A walk is a sequence of vertices in which each consecutive pair is joined by an edge. A trail is a walk that repeats no edge. A path is a walk that repeats no vertex. A cycle is a path that returns to its starting vertex, with no other vertex repeated; in a simple graph a cycle needs at least three vertices. A graph is connected when every pair of vertices is joined by a path. A disconnected graph falls into separate pieces called components, such as two friendship groups that share no members.

Graphs with names

Some graphs appear so often that they have names. The complete graph \(K_n\) has \(n\) vertices with every pair adjacent, so it has

\binom{n}{2} = \frac{n(n-1)}{2}

edges; \(K_5\) has 10. The cycle \(C_n\) is \(n\) vertices joined in a ring. The path \(P_n\) is a single path with \(n\) edges in this course (some books count vertices instead). A graph is bipartite when its vertices split into two sets with every edge running between the sets. The complete bipartite graph \(K_{m,n}\) joins each of \(m\) vertices to each of \(n\) others, giving \(mn\) edges.

Subgraphs

A subgraph of \(G\) is a graph whose vertices and edges all belong to \(G\). You may delete vertices, which deletes their edges too, and you may delete edges while keeping their ends. An induced subgraph keeps a chosen set of vertices and every edge of \(G\) between them. For example, in \(K_4\) with vertices \(a, b, c, d\), the subgraph induced by \(a, b, c\) is a triangle, while the path \(a\)-\(b\)-\(c\) on its own is a subgraph that is not induced, because it leaves out the edge \(ac\).

Storing a graph

Without pictures, graphs are written as lists. An adjacency list gives each vertex with its neighbours, for example a: b, c; b: a; c: a. An adjacency matrix has a row and a column for each vertex, with a 1 where the two vertices are adjacent and a 0 otherwise. For a simple undirected graph the matrix is symmetric with 0s on the diagonal, and each row sums to that vertex's degree. Lists use less memory when edges are few, which is true of most large real networks; a matrix answers "are these two adjacent?" in one lookup.

Worked example: the same graph in disguise

Two graphs are isomorphic when there is a one-to-one correspondence between their vertices that keeps adjacent pairs adjacent and non-adjacent pairs non-adjacent. 1. Let \(G\) have edges \(ab, bc, cd, de, ea\), and \(H\) have edges 13, 35, 52, 24, 41. 2. Follow \(H\) from vertex 1: 1, 3, 5, 2, 4 and back to 1, so \(H\) is also a 5-cycle. 3. Map \(a \to 1\), \(b \to 3\), \(c \to 5\), \(d \to 2\), \(e \to 4\). Each edge of \(G\) becomes an edge of \(H\): \(ab \to 13\), \(bc \to 35\), \(cd \to 52\), \(de \to 24\), \(ea \to 41\). 4. Both have 5 edges, so nothing is missed: \(G\) and \(H\) are isomorphic.

Telling graphs apart

To show two graphs are not isomorphic, find an invariant, a property that isomorphic graphs always share, on which they differ. Useful invariants are the number of vertices, the number of edges, the list of degrees, connectedness and the lengths of cycles present. Matching invariants prove nothing, though. The cycle \(C_6\) and a pair of separate triangles both have 6 vertices, 6 edges and every degree equal to 2, yet \(C_6\) is connected and the triangles are not, so they are not isomorphic.

Common mistakes to avoid

First, reading meaning into a drawing: two edges that cross on paper do not meet at a vertex, and a different layout can be the same graph. Second, confusing the degree sum with the number of edges; the sum is twice the edge count. Third, treating an even degree sum as proof that a graph exists, when the degrees can still be impossible. Fourth, concluding that two graphs are isomorphic because their degrees match. Fifth, mixing up path and walk: a path never revisits a vertex.

Key takeaways

A graph is a set of vertices and a set of edges joining pairs of them; only adjacency matters, not the drawing. The degree sum equals twice the number of edges, so the number of odd-degree vertices is even. Walks, trails, paths and cycles describe routes, and connectedness asks whether every pair is joined by a path. \(K_n\) has \(n(n-1)/2\) edges and \(K_{m,n}\) has \(mn\). Isomorphic graphs share every invariant; one differing invariant proves two graphs are different.

Flashcards

Flashcard

G = (V, E)

A graph: a vertex set V and an edge set E of pairs of vertices

Only which pairs are joined matters.

Test your understanding

Question 1 of 5

A graph has vertex degrees 5, 4, 3, 3, 2 and 1. How many edges does it have?

Question 2 of 5

How many edges does the complete graph K₈ have?

Question 3 of 5

Which list of degrees cannot belong to any graph?

Question 4 of 5

A graph G has 6 vertices, each of degree 2. Which statement must be true?

Question 5 of 5

In the adjacency matrix of a simple undirected graph, what does the sum of the entries in the row for vertex v equal?

← Previous topicNext topic →