Part I · Foundations

The Basics

Created by Felipe Casadei

A graph is a set of dots and a set of connections between pairs of dots. Nothing else. After this chapter you will be able to read the notation used in every later chapter, measure a network in half a dozen different ways, and prove the theorem that started the subject in 1736.

Why dots and lines are enough

Throw away the geography of a subway map and keep only which stations are joined by a direct segment of track. What survives is a graph: things, called vertices, plus a record of which pairs are linked, called edges. It carries no distances, directions, weights, or positions.

The chapter's larger job is vocabulary: graphs, degree, paths, connectivity, trees, bipartite graphs, minors, and Euler tours build the language the rest of the book speaks. The second job arrives near the end, where the cycles and the cuts of a graph turn out to be two vector spaces, each the orthogonal complement of the other. Underneath both sits one habit of thought: graph theory defines numerical measurements, called invariants, then asks how one forces another. Almost every theorem here has that shape, a number on the left and a structure you are guaranteed to find on the right.

One warning first. Diestel writes the complete graph on \(n\) vertices as \(K^n\), index raised, where most books write \(K_n\); likewise for \(P^k\) and \(C^k\). The subscript slot is kept free for counting, so \(C_1, C_2, C_3\) can name three cycles while \(C^5\) names the cycle of length five. If the set language below is unfamiliar, Chapter 0 teaches it from scratch.

New notation in this chapter

This is the densest notation table in the course, because almost every symbol in the book is introduced here. Skim it now and return to it as a reference; the sections below reintroduce each symbol in context, with examples.

Graphs and how to draw them

Everything starts with one definition, and that definition quietly makes three modelling decisions on your behalf.

Two counts come up constantly. The order \(|G|\) is the number of vertices, single bars; the size \(\|G\|\) is the number of edges, double bars. A graph of order 0 or 1 is trivial.

Two vertices joined by an edge are adjacent, or neighbours. Two edges are adjacent when they share an end. A set of vertices no two of which are adjacent is independent. The opposite extreme has its own name.

When are two graphs "the same"? If one becomes the other by renaming vertices, we write \(G \simeq G'\) and call them isomorphic: formally, a one-to-one correspondence \(\varphi\) between the vertex sets with \(xy\) an edge of \(G\) exactly when \(\varphi(x)\varphi(y)\) is an edge of \(G'\). Diestel usually writes \(=\) here. A graph property is any statement surviving renaming, such as "contains a triangle"; a graph invariant is any number surviving renaming, and invariants are the measurements this book compares.

Subgraphs, induced subgraphs, and the other operations

Five more operations complete the toolkit. Vertex deletion \(G - U\) removes those vertices and every edge touching them; edge deletion \(G - F\) removes edges only, and \(G + F\) adds them. The join \(G * G'\) adds every edge between two disjoint graphs, so \(K^2 * K^3 = K^5\); the complement \(\overline{G}\) flips every adjacency; and the line graph \(L(G)\) turns the edges of \(G\) into vertices, joined whenever those edges shared an end.

Degree: counting at a single vertex

The simplest measurement of a network is local: stand at one dot and count the lines leaving it.

From those local counts come four global numbers: the minimum degree \(\delta(G)\), the maximum degree \(\Delta(G)\), the average degree \(d(G)\), which divides the degree total by \(|G|\), and the edge density \(\varepsilon(G) := \|G\|/|G|\), which is half the average degree. Always \(\delta(G) \le d(G) \le \Delta(G)\). A graph is \(k\)-regular when every degree equals \(k\), and cubic when \(k=3\).

Proof idea, pure bookkeeping. Count the pairs made of an edge together with one of its ends: vertex by vertex the total is \(\sum_v d(v)\), edge by edge it is \(2\|G\|\). The total is therefore even, and a sum of whole numbers is even only if an even number of its terms are odd.

The second result converts a statement about an average into one about every single vertex.

Proof idea. Repeatedly delete any vertex whose degree is at most the current edge density. Each deletion costs one vertex and at most \(\varepsilon\) edges, so the ratio never falls, and the process cannot run to the end. When it halts, no deletable vertex remains, which is exactly \(\delta(H) > \varepsilon(H)\).

Paths, cycles, and distance

Diestel gives paths a compact naming system. Write \(P = x_0x_1\dots x_k\); then \(x_iPx_j\) is the stretch between those vertices, and a small ring strips off ends, so if \(P = abcde\) then \(\mathring{P} = bcd\), as does \(bPd\). An expression like \(PxQyR\) means "along \(P\) to \(x\), along \(Q\) to \(y\), then along \(R\)".

Two more path types get names because separation arguments need them. An \(A\)–\(B\) path meets \(A\) only in its first vertex and \(B\) only in its last. Paths are independent when none contains an inner vertex of another, the notion Menger's theorem needs in Chapter 3.

Those two numbers are locked together. Clearly \(\operatorname{rad}(G) \le \operatorname{diam}(G)\). In the other direction, route any trip from \(x\) to \(y\) through a central vertex \(z\), costing at most \(d(x,z) + d(z,y) \le 2\operatorname{rad}(G)\). So \(\operatorname{rad}(G) \le \operatorname{diam}(G) \le 2\operatorname{rad}(G)\), and Figure 1.11 attains the upper bound twice over, while a four-cycle, with radius and diameter both 2, sits at the other end.^[3]

A walk is the loose cousin of a path: an alternating sequence \(v_0e_0v_1\dots v_k\) where each \(e_i\) joins \(v_i\) to \(v_{i+1}\), repeats allowed, and closed when it ends where it started. The bridge between the two: every walk from \(x\) to \(y\) contains an \(x\)–\(y\) path inside it, found by cutting out the closed sections it made.

A bound runs the other way too. Layering a graph by distance from a central vertex lets each layer grow by a factor of at most \(\Delta(G)-1\), capping the order of any graph of small radius and bounded degree. Theorem 1.3.4 of Alon, Hoory and Linial pushes this to average degree and yields a memorable corollary: if \(\delta(G) \ge 3\) then \(g(G) < 2\log|G|\), with \(\log\) base 2 throughout.^[3]

Connectivity: how hard is the network to break

Connected graphs can be assembled one vertex at a time. Diestel's Proposition 1.4.1 lists the vertices of a connected \(G\) as \(v_1, \dots, v_n\) so that every initial stretch \(G[\{v_1,\dots,v_i\}]\) is connected, which is what drives induction on connected graphs.^[4]

Bridges have a clean alternative description worth memorising: an edge is a bridge exactly when it lies on no cycle. On a cycle, its ends stay joined the long way round.

Proof idea. The right inequality is one line: cut all \(\delta(G)\) edges at a vertex of smallest degree and it is isolated. For the left, start from a smallest disconnecting edge set \(F\). If some vertex \(v\) touches none of \(F\), the vertices on \(v\)'s side that do touch \(F\)-edges form a separator of at most \(|F|\) members; otherwise \(d(v) \le |F|\) and \(N(v)\) separates \(v\), unless \(v\) is adjacent to every other vertex, in which case \(G\) is complete and \(\kappa = \lambda = |G| - 1\).

Proof idea. Among all subgraphs that are large enough and satisfy a chosen edge-count inequality, take a smallest one, \(H\); minimality then forces both a high minimum degree and the absence of any small separation. The full argument is in Diestel §1.4. This is the flagship demonstration that a numerical average forces qualitative structure, and it returns in Chapter 7 and Chapter 12.

Trees and forests

Connect \(n\) sites with as few links as possible and you get a tree. Trees are the most useful special case in the subject, appearing as objects of study, as proof scaffolding, and as data structures.

Proof idea. Build the tree one vertex at a time: with no cycles, each new vertex arrives attached by exactly one edge, so \(n\) vertices cost \(n-1\) edges. Conversely, every connected graph contains a spanning tree, a subgraph that is a tree using every vertex. That tree already uses \(n-1\) edges, so a graph with only \(n-1\) is the tree. Edges outside a spanning tree \(T\) are its chords, and they star in the linear algebra section.

Trees are also the cheapest shapes to find inside other graphs: by Corollary 1.5.3, \(\delta(G) \ge |T| - 1\) already forces a copy of the tree \(T\), built greedily one vertex at a time. Forcing a clique needs far more, as Chapter 7 shows.^[5]

Rooted trees, tree-order, and the two closures

Pick one vertex of a tree and call it the root: that turns the tree into a hierarchy. Define \(x \le y\) to mean \(x\) lies on the unique path \(rTy\). In this tree-order the root is below everything and the leaves are maximal, even though the drawing puts the root at the top, as trees are almost always drawn. Vertices in different branches are incomparable. The height of a vertex is its distance from the root, and all vertices of height \(k\) form the \(k\)-th level.

That last distinction has a name and a payoff. A rooted tree \(T \subseteq G\) is normal in \(G\) when the two ends of every path of \(G\) that leaves and re-enters \(T\) are comparable in the tree-order. Plainly, the host graph's edges run only up and down the tree, never sideways between branches. These are exactly the trees a depth-first search produces.^[5]

Bipartite graphs

Two examples worth knowing on sight. \(K_{3,3}\) is the three-houses-three-utilities graph, and one of the two obstacles to crossing-free drawing in Chapter 4. \(K_2^3 = K_{2,2,2}\) is the octahedron: six vertices in three opposite pairs, each joined to all but its partner.

Proof idea. One direction is a walk around a cycle: every step switches camps, so after an odd number of steps you cannot be home. For the other, take a spanning tree \(T\) rooted at \(r\) and colour each vertex \(v\) by whether \(rTv\) has even or odd length; tree edges then join opposite colours automatically. A non-tree edge \(xy\) closes a cycle one longer than \(xTy\), and that cycle is even by hypothesis, so \(x\) and \(y\) already differ.

Contraction and minors

"Contains" has more than one useful meaning, and subgraphs are the strictest. This section adds two looser notions, both of which find a shape inside a graph even when no literal copy is present.

Three facts organize the theory. First, both relations behave like an ordering: every graph is a minor of itself, two different graphs cannot each be a minor of the other, and a minor of a minor is a minor. Second, Diestel's Corollary 1.7.2 gives the hands-on version used in practice: \(X\) is a minor of \(Y\) exactly when you can get from \(Y\) to \(X\) by deleting vertices, deleting edges, and contracting edges. Third, every topological minor is a minor, and when the smaller graph has maximum degree at most 3 the two coincide.^[7]

Euler tours

In Königsberg, seven bridges connected two river banks and two islands, and the residents asked whether a walk could cross every bridge exactly once and finish where it began. In 1736 Leonhard Euler proved that it could not, and his argument is generally counted as the first theorem of graph theory.

Before you read Euler's answer, try the walk. The map below is the 1736 city, and the seven bridges carry the names Königsberg gave them. Click a landmass to stand on it, then click bridges to cross them, one at a time and each one only once. After two failed attempts the map offers to show you what keeps going wrong.

The adjacency and incidence matrices, cycle space and cut space

All of this is arithmetic modulo 2, in the two-element field \(\mathbb{F}_2\) where \(1 + 1 = 0\). Think of each edge as carrying a switch: adding a set of edges flips those switches, and flipping twice returns you to the start, which is the rule \(F + F = \emptyset\).

The edge space also carries an inner product: \(\langle F, F' \rangle\) is 0 when the two sets share an even number of edges and 1 when odd. For a subspace \(\mathcal{F}\), the orthogonal complement \(\mathcal{F}^{\perp}\) is everything meeting every member of \(\mathcal{F}\) evenly, and \(\dim \mathcal{F} + \dim \mathcal{F}^{\perp} = \|G\|\).

Cuts assemble from the simplest ones. The atomic cut \(E(v)\) is the bundle of all edges at one vertex, and Proposition 1.9.2 says the cuts form a subspace generated by these: the cut with sides \(V_1\) and \(V_2\) is the sum of \(E(v)\) over \(v \in V_1\), since edges inside \(V_1\) are counted twice and cancel. Lemma 1.9.3 adds that every cut splits into bonds.^[9]

Proof idea. Half of it is one observation: walk around a cycle and count how often you cross a given split of the vertices; you end where you began, so you crossed evenly. An edge set outside the cycle space has a vertex of odd degree, so it meets the atomic cut there oddly. The subtle step is the last: given \(F\) meeting every cycle evenly, contract every edge not in \(F\); the result has no odd cycle, so it splits into two camps, and pulling that split back exhibits \(F\) as a cut.

Proof idea. Independence is immediate, since the chord \(e\) appears in \(C_e\) and no other fundamental cycle. For spanning, add to any cycle \(C\) the fundamental cycle of each of its chords: the result lies in the cycle space but uses only tree edges, and the only such element is the empty set. The dimensions follow from the tree edge count \(n-1\), and \(m - n + 1\) is called the cyclomatic number.

Finally, the matrices. The incidence matrix \(B\) has one row per vertex and one column per edge, with a 1 wherever the vertex lies on the edge. The adjacency matrix \(A\) has a 1 wherever two vertices are joined, and its row sums are the degrees. The degree matrix \(D\) lists the degrees down its diagonal. Over \(\mathbb{F}_2\), \(B\) sends an edge set to the vertices meeting an odd number of its edges and \(B^{\top}\) sends a vertex set \(U\) to the edges with one end in \(U\), so the kernel of \(B\) is the cycle space and the image of \(B^{\top}\) is the cut space.^[9] Over the real numbers \(BB^{\top} = A + D\), and with directions on the edges it becomes \(D - A\), the Laplacian behind spectral graph theory, spectral clustering and graph neural networks.

Other notions of graphs: directed, multigraphs, hypergraphs

An orientation chooses one of the two directions for each edge of an ordinary graph, and a digraph arising this way is an oriented graph. Flows in Chapter 6 and the tournament results in Chapter 10 live in that setting.

Multigraphs reuse most of the vocabulary, with three differences. Cycles of length 1 and 2 now exist, being a loop and a doubled edge. A loop contributes 2 to its vertex's degree, so degree and neighbour count stop agreeing, and it makes its vertex a cutvertex, so every 3-connected multigraph is an ordinary graph. Contraction gets simpler, since contracting \(e\) deletes no other edge. Plane duality in Chapter 4 and flows in Chapter 6 force multigraphs into the story anyway.^[10]

One last note. Authors who take multigraphs as their default call the objects of this chapter simple graphs, so check which convention a paper uses before believing any degree count.

What to carry forward

Four things from this chapter appear on nearly every later page. First, the notation, which is why the table near the top exists and why ten other chapters link to it. Learn to read \(|G|\) and \(\|G\|\) apart, and remember that Diestel's indices ride high.

Second, the double-counting reflex: the degree-sum identity came from counting one set of pairs in two ways. Third, the extremal-choice reflex: take a longest path or a smallest counterexample, then ask what the extreme case cannot do. Proposition 1.3.1, Mader's theorem, Euler's theorem and the existence of normal spanning trees are all built that way.

Fourth, the shape of a good theorem. Euler's theorem reduces a global traversal question to a local parity check; the bipartite theorem reduces a two-camp question to one forbidden shape. Characterisations of that kind, where a property you cannot see is equivalent to one you can check, are what the rest of the book hunts, and Chapter 2 starts that hunt with matchings.