Reference
Master Notation Table
Every symbol used in this course, in the order the chapters introduce it. A symbol appears once, under the chapter that first defines it. Use the search box to jump to a symbol by name, by how it is read aloud, or by what it means.
Searching filters rows across every chapter below. Clear the box to see everything again.
How to use this page
Mathematical notation is compression, not decoration. Each row here gives four things: the symbol, how to say it out loud, what it means in plain words, and a small example. Reading a formula aloud is the single most useful habit for learning to read mathematics, which is why the second column exists. If a symbol here still feels opaque, follow its chapter link: the chapter introduces it with motivation and a picture.
Chapter 0: How to Read Mathematics
37 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\{a, b, c\}\) | "the set a, b, c" | The collection whose members are exactly \(a\), \(b\), \(c\). Order and repetition do not matter. | \(\{2,1\} = \{1,2\} = \{1,1,2\}\) |
| \(x \in A\) | "x is in A" / "x is an element of A" | \(x\) is one of the members of the set \(A\). | \(2 \in \{1,2,3\}\) |
| \(x \notin A\) | "x is not in A" | \(x\) is not a member of \(A\). | \(5 \notin \{1,2,3\}\) |
| \(\emptyset\) | "the empty set" | The set with no members at all. | \(\{x \in \mathbb{N} : x < 0\} = \emptyset\) |
| \(A \subseteq B\) | "A is a subset of B" | Every member of \(A\) is also a member of \(B\). | \(\{1,2\} \subseteq \{1,2,3\}\) |
| \(A \subsetneq B\) | "A is a proper subset of B" | \(A \subseteq B\) and \(A \neq B\): \(B\) has at least one extra member. | \(\{1\} \subsetneq \{1,2\}\) |
| \(A \cup B\) | "A union B" | The set of everything in \(A\) or in \(B\) (or both). | \(\{1,2\} \cup \{2,3\} = \{1,2,3\}\) |
| \(A \cap B\) | "A intersect B" | The set of everything in both \(A\) and \(B\). | \(\{1,2\} \cap \{2,3\} = \{2\}\) |
| \(A \setminus B\) | "A minus B" | The members of \(A\) that are not in \(B\). | \(\{1,2,3\} \setminus \{2\} = \{1,3\}\) |
| \(\{x : P(x)\}\) | "the set of all x such that P holds" | Set-builder notation: collect exactly the objects with property \(P\). | \(\{x \in \mathbb{N} : x \text{ is even}\}\) |
| \(|A|\) | "the size of A" | The number of elements of \(A\) (its cardinality). | \(|\{a,b,c\}| = 3\), \(|\emptyset| = 0\) |
| \(\mathbb{N}\) | "the natural numbers" | \(\{0, 1, 2, 3, \dots\}\). In this course, following Diestel, zero is included. | \(0 \in \mathbb{N}\) |
| \(\mathbb{Z}\) | "the integers" | All whole numbers: \(\{\dots,-2,-1,0,1,2,\dots\}\). | \(-3 \in \mathbb{Z}\), \(-3 \notin \mathbb{N}\) |
| \(\mathbb{R}\) | "the real numbers" | All points on the number line, including fractions and irrationals. | \(\sqrt{2} \in \mathbb{R}\) |
| \([a, b]\) | "the interval from a to b" | All real numbers from \(a\) to \(b\), endpoints included; \((a,b)\) excludes them. | \(2.5 \in [2,3]\) |
| \([n]\) | "the set one up to n" | Shorthand for \(\{1, 2, \dots, n\}\). | \([3] = \{1,2,3\}\) |
| \(\lfloor x \rfloor\) | "the floor of x" | \(x\) rounded down to the nearest integer. | \(\lfloor 2.9 \rfloor = 2\) |
| \(\lceil x \rceil\) | "the ceiling of x" | \(x\) rounded up to the nearest integer. | \(\lceil 2.1 \rceil = 3\) |
| \((a, b)\) | "the ordered pair a, b" | Two objects with a first and a second; order matters. | \((1,2) \neq (2,1)\) |
| \(A \times B\) | "A cross B" | The set of all ordered pairs with first entry from \(A\), second from \(B\). | \(\{1,2\} \times \{x\} = \{(1,x),(2,x)\}\) |
| \([A]^2\) | "the 2-element subsets of A" | The set of all unordered pairs of distinct elements of \(A\). Diestel's notation; edges of a graph live here. | \([\{a,b,c\}]^2 = \{\{a,b\},\{a,c\},\{b,c\}\}\) |
| \(f\colon A \to B\) | "f from A to B" | A function: a rule assigning to each element of \(A\) exactly one element of \(B\). | \(f\colon \mathbb{N} \to \mathbb{N}\), \(f(x) = x^2\) |
| \(f(A')\) | "the image of A' under f" | The set of outputs \(f\) produces on inputs from \(A' \subseteq A\). | for \(f(x)=x^2\): \(f(\{1,2\}) = \{1,4\}\) |
| \(f^{-1}(y)\) | "the preimage of y" | The set of inputs that \(f\) sends to \(y\). | for \(f(x)=x^2\) on \(\mathbb{Z}\): \(f^{-1}(4) = \{-2,2\}\) |
| \(g \circ f\) | "g after f" / "g composed with f" | Apply \(f\) first, then \(g\): \((g \circ f)(x) = g(f(x))\). | \(f(x)=x+1,\ g(x)=2x\): \((g\circ f)(3)=8\) |
| \(\min A\), \(\max A\) | "the minimum / maximum of A" | The smallest / largest element of a set of numbers. | \(\min\{4,1,7\} = 1\) |
| \(\sum_{i=1}^{n} a_i\) | "the sum over i from 1 to n of a-i" | Add up the terms \(a_1 + a_2 + \dots + a_n\). | \(\sum_{i=1}^{4} i = 10\) |
| \(\prod_{i=1}^{n} a_i\) | "the product over i from 1 to n" | Multiply the terms \(a_1 \cdot a_2 \cdots a_n\). | \(\prod_{i=1}^{4} i = 24\) |
| \(\binom{n}{k}\) | "n choose k" | The number of \(k\)-element subsets of an \(n\)-element set. | \(\binom{4}{2} = 6\) |
| \(\forall\) | "for all" | The claim that follows holds for every object in view. | \(\forall n \in \mathbb{N}: n \ge 0\) |
| \(\exists\) | "there exists" | At least one object with the stated property exists. | \(\exists n \in \mathbb{N}: n^2 = 49\) |
| \(P \Rightarrow Q\) | "P implies Q" / "if P then Q" | Whenever \(P\) is true, \(Q\) must also be true. | \(x > 2 \Rightarrow x > 1\) |
| \(P \Leftrightarrow Q\) | "P if and only if Q" | \(P\) and \(Q\) are true in exactly the same cases ("iff"). | \(x \text{ even} \Leftrightarrow x+2 \text{ even}\) |
| \(\neg P\) | "not P" | The claim that \(P\) is false. | \(\neg(3 > 5)\) is true |
| \(O(n^2)\) | "big-O of n squared" | Grows no faster than a constant times \(n^2\), for large \(n\). | \(5n^2 + 3n\) is \(O(n^2)\) |
| \(o(1)\) | "little-o of one" | A quantity that shrinks to \(0\) as \(n\) grows. | \(1/n\) is \(o(1)\) |
| \(\log n\) | "log n" | Logarithm base 2 in this course, following Diestel: the power you raise 2 to in order to get \(n\). | \(\log 8 = 3\) |
Chapter 1: The Basics
54 new symbols (2 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\mathbb{F}_2\) | "the field with two elements" | The number system \(\{0,1\}\) with arithmetic done modulo 2, so \(1+1=0\). | Used for every vector space in the last big section. |
| \(\lfloor x \rfloor\), \(\lceil x \rceil\) | "floor of x", "ceiling of x" | Round a number down, round a number up. | \(\lfloor 2.7 \rfloor = 2\), \(\lceil 2.1 \rceil = 3\). |
| \([A]^k\) | "the k-subsets of A" | The set of all subsets of \(A\) with exactly \(k\) elements. | \([\{1,2,3\}]^2 = \{\{1,2\},\{1,3\},\{2,3\}\}\). |
| \(x := y\) | "x is defined to be y" | A definition, not an equation to be solved. The colon sits on the side being named. | \(\varepsilon(G) := \|G\|/|G|\). |
| \(G = (V,E)\) | "the graph G with vertices V and edges E" | A graph is a pair of sets: dots, and unordered pairs of distinct dots. | \(G = (\{1,2,3\},\{\{1,2\},\{2,3\}\})\). |
| \(V(G)\), \(E(G)\) | "the vertices of G", "the edges of G" | Always written this way, whatever letters were used to define the graph. | If \(H=(W,F)\), its vertex set is still \(V(H)\). |
| \(|G|\) | "the order of G" | How many vertices \(G\) has. Single bars count dots. | \(|K^5| = 5\). |
| \(\|G\|\) | "the size of G" | How many edges \(G\) has. Double bars count links. | \(\|K^5\| = 10\). |
| \(xy\) | "the edge from x to y" | Shorthand for the edge \(\{x,y\}\). Since the pair is unordered, \(xy = yx\). | The triangle has edges \(ab, bc, ca\). |
| \(K^n\) | "K n", the complete graph | \(n\) vertices with every possible edge present. \(K^3\) is a triangle. Note the raised index. | \(\|K^4\| = \binom{4}{2} = 6\). |
| \(G \simeq H\) | "G is isomorphic to H" | Same graph after renaming the vertices. Diestel often just writes \(=\). | Any two triangles are isomorphic. |
| \(G' \subseteq G\) | "G prime is a subgraph of G" | Every vertex and every edge of \(G'\) is also in \(G\). | Every path in \(G\) is a subgraph of \(G\). |
| \(G[U]\) | "G induced on U" | Keep the vertices in \(U\) and all edges of \(G\) with both ends in \(U\). | In a triangle \(abc\), \(G[\{a,b\}]\) is the single edge \(ab\). |
| \(G - U\), \(G - v\) | "G minus U", "G minus v" | Delete those vertices and every edge touching them. | Deleting a star's centre leaves lone vertices. |
| \(G - e\), \(G + e\) | "G minus e", "G plus e" | Remove or add one edge, keeping every vertex in place. | \(C^4 + e\) with \(e\) a diagonal is a square with a chord. |
| \(G \cup G'\), \(G \cap G'\) | "G union G prime", "G intersect G prime" | Take unions (or intersections) of both the vertex sets and the edge sets. | \(G \cap G' = \emptyset\) means the two graphs are disjoint. |
| \(G * G'\) | "the join of G and G prime" | Two disjoint graphs plus every edge running between them. | \(K^2 * K^3 = K^5\). |
| \(\overline{G}\) | "the complement of G" | Same vertices; two are joined exactly when they were not joined in \(G\). | \(\overline{K^n}\) has no edges at all. |
| \(L(G)\) | "the line graph of G" | Its vertices are the edges of \(G\); two are joined when those edges share an end. | \(L(K^3) = K^3\). |
| \(E(X,Y)\), \(E(v)\) | "the edges between X and Y", "the edges at v" | Edges with one end in \(X\) and the other in \(Y\); edges touching the single vertex \(v\). | \(d(v) = |E(v)|\). |
| \(N(v)\), \(N(U)\) | "the neighbourhood of v", "of U" | The vertices joined to \(v\) by an edge. For a set \(U\), the vertices outside \(U\) with a neighbour inside it. | In \(K^4\), \(|N(v)| = 3\) for every \(v\). |
| \(d(v)\) | "the degree of v" | How many edges touch \(v\); equivalently, how many neighbours it has. | An isolated vertex has \(d(v)=0\). |
| \(\delta(G)\) | "delta of G", the minimum degree | The smallest degree anywhere in \(G\). | \(\delta(C^5) = 2\). |
| \(\Delta(G)\) | "big delta of G", the maximum degree | The largest degree anywhere in \(G\). | \(\Delta(K_{1,n}) = n\). |
| \(d(G)\) | "the average degree of G" | The degrees added up and divided by the number of vertices. Always \(\delta \le d \le \Delta\). | Every cycle has \(d(G) = 2\). |
| \(\varepsilon(G)\) | "epsilon of G", the edge density | Edges per vertex, \(\|G\|/|G|\). It always equals half the average degree. | A tree on \(n\) vertices has \(\varepsilon = (n-1)/n\). |
| \(P^k\) | "P k", the path of length k | A path with \(k\) edges, hence \(k+1\) vertices. The index is the edge count. | \(P^2\) has 3 vertices. |
| \(xPy\), \(\mathring{P}\) | "the piece of P from x to y", "P without its ends" | Names a stretch of a path. The small ring strips off the end vertices. | If \(P = abcde\) then \(bPd = bcd\) and \(\mathring{P} = bcd\). |
| \(C^k\) | "C k", the cycle of length k | A round trip through \(k\) distinct vertices, using \(k\) edges. Needs \(k \ge 3\). | \(C^3 = K^3\), the triangle. |
| \(g(G)\) | "the girth of G" | The length of the shortest cycle; \(\infty\) if there is no cycle. | \(g(K^4) = 3\); any tree has \(g = \infty\). |
| \(d(x,y)\) | "the distance from x to y" | The number of edges on a shortest path between them; \(\infty\) if no path exists. | Opposite corners of \(C^6\) are at distance 3. |
| \(\operatorname{diam}(G)\) | "the diameter of G" | The largest distance between any two vertices: the worst case. | \(\operatorname{diam}(K^n) = 1\) for \(n \ge 2\). |
| \(\operatorname{rad}(G)\) | "the radius of G" | Stand at the best-placed vertex; the radius is how far the farthest vertex still is. | A star has radius 1 and diameter 2. |
| \(\{A,B\}\) | "a separation of G" | Two vertex sets covering \(V\) with no edge crossing between the parts outside their overlap. Its order is \(|A \cap B|\). | A cutvertex \(v\) gives a separation with \(A \cap B = \{v\}\). |
| \(\kappa(G)\) | "kappa of G", the connectivity | The largest \(k\) such that no removal of fewer than \(k\) vertices breaks the graph apart. | \(\kappa(K^n) = n-1\). |
| \(\lambda(G)\) | "lambda of G", the edge-connectivity | The same idea counting edges: how many links must be cut to disconnect it. | \(\lambda(C^n) = 2\); a bridge forces \(\lambda = 1\). |
| \(xTy\) | "the tree path from x to y" | In a tree there is exactly one path between any two vertices, and this names it. | In a star with centre \(c\), \(xTy = xcy\). |
| \(x \le y\) | "x lies below y in the tree" | In a tree with a chosen root, \(x\) sits on the path from the root up to \(y\). | The root lies below every vertex. |
| \(\lceil y \rceil\) | "the down-closure of y" | The vertex \(y\) plus everything on its path back to the root. Nothing to do with ceilings of numbers. | For a leaf \(y\), this is the whole root-to-\(y\) path. |
| \(K_{n_1,\dots,n_r}\) | "the complete r-partite graph" | Vertices split into \(r\) groups of the stated sizes; two vertices are joined exactly when they are in different groups. | \(K_{3,3}\) is the three-houses-three-utilities graph. |
| \(K_s^r\) | "K s upper r" | The balanced case: \(r\) groups, each of size \(s\). | \(K_2^3 = K_{2,2,2}\) is the octahedron. |
| \(K_{1,n}\) | "the star with n leaves" | One centre joined to \(n\) other vertices and nothing else. | \(K_{1,3}\) is called the claw. |
| \(TX\) | "a subdivision of X" | Take \(X\) and redraw some edges as longer paths with new vertices on them. The letter T stands for topological. | \(C^{17}\) is a subdivision of the triangle. |
| \(IX\) | "an inflated X" | Take \(X\) and blow each vertex up into a connected blob, keeping at least one edge between blobs that were joined. | Three connected blobs, pairwise joined, form an \(IK^3\). |
| \(X \preccurlyeq Y\) | "X is a minor of Y" | Some subgraph of \(Y\) is an inflated copy of \(X\). | \(K^5 \preccurlyeq\) the Petersen graph. |
| \(G/e\), \(G/P\) | "G contract e", "G contract the partition P" | Merge the two ends of the edge \(e\) into one new vertex; more generally squash each class of \(P\) to a point. | \(C^4/e = C^3\) for any edge \(e\). |
| \(\mathcal{E}(G)\), \(\mathcal{V}(G)\) | "the edge space", "the vertex space" | All sets of edges (or of vertices), treated as vectors. Adding two sets means keeping exactly what lies in one of them but not both. | \(F + F = \emptyset\) for every edge set \(F\). |
| \(\langle F, F' \rangle\) | "the inner product of F and F prime" | 0 when the two edge sets share an even number of edges, 1 when they share an odd number. | Any set of even size is orthogonal to itself. |
| \(\mathcal{F}^{\perp}\) | "F perp", the orthogonal complement | Everything that meets every member of \(\mathcal{F}\) in an even number of edges. | The cycle space and cut space are each other's perp. |
| \(\mathcal{C}(G)\) | "the cycle space of G" | All edge sets you can build by adding cycles together. | For connected \(G\), its dimension is \(\|G\| - |G| + 1\). |
| \(\mathcal{B}(G)\) | "the cut space of G" | All edge sets that cross a split of the vertices into two parts, plus the empty set. | For connected \(G\), its dimension is \(|G| - 1\). |
| \(C_e\), \(D_f\) | "the fundamental cycle of e", "the fundamental cut of f" | Fix a spanning tree. Each non-tree edge closes exactly one cycle; each tree edge splits the tree and defines one cut. | \(f \in C_e\) happens exactly when \(e \in D_f\). |
| \(A\), \(B\), \(D\) | "adjacency, incidence, degree matrix" | \(A\) records which pairs of vertices are joined; \(B\) records which vertices lie on which edges; \(D\) lists the degrees down its diagonal. | \(BB^{\top} = A + D\). |
| \(\operatorname{init}(e)\), \(\operatorname{ter}(e)\) | "the initial and terminal vertex of e" | In a directed graph, where the arrow starts and where it points. | A one-way street from junction \(x\) to junction \(y\). |
Chapter 2: Matching, Covering and Packing
13 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(M\) | "the matching M" | The standard letter for a matching: a set of edges of which no two share an endpoint. | In a square with corners 1,2,3,4, the edge set \(\{12, 34\}\) is a matching. |
| \(N(S)\) | "the neighbourhood of S" | (From Chapter 1.) The set of all vertices that have at least one neighbour inside the set \(S\). | If \(a_1\) knows \(b_1\) and \(a_2\) knows \(b_1, b_2\), then \(N(\{a_1,a_2\}) = \{b_1, b_2\}\). |
| \(q(G)\) | "the number of odd components of G" | How many connected pieces of \(G\) have an odd number of vertices. | A lone vertex plus a triangle plus a square: \(q = 2\). |
| \(\mathcal{C}_G\) | "the components of G" | The set whose members are the connected pieces of \(G\). | Two separate triangles: \(\mathcal{C}_G\) has 2 members. |
| \(G_S\) | "G contracted onto S" | Squash each component of \(G - S\) to a single point and delete the edges inside \(S\): a bipartite graph with \(S\) on one side and the shrunken components on the other. | Used in the Gallai–Edmonds theorem; see Figure 2.9. |
| \(e <_v f\) | "v prefers f to e" | In a set of preferences, each vertex \(v\) ranks the edges ending at it; this says \(v\) strictly prefers edge \(f\) to edge \(e\). | Worker \(a\) may rank \(ab_1 <_a ab_2\), preferring job \(b_2\). |
| \(\mathcal{H}\) | "the class H" | A collection of target shapes for packing and covering, such as the class of all cycles. | With \(\mathcal{H}\) = all cycles, packing means finding disjoint cycles. |
| \(f(k)\) | "f of k" | A bound that depends only on the number \(k\), never on the graph. | In the Erdős–Pósa theorem, \(f(k)\) grows like \(4k\log k\). |
| \(\mathcal{T} = (T_1, \dots, T_k)\) | "a family of spanning trees" | An indexed list of \(k\) spanning trees of a graph; repeats are allowed. | Two different spanning paths of a square form a family with \(k = 2\). |
| \(E(\mathcal{T})\) | "the edges of the family" | Every edge that lies on at least one tree of the family, each counted once. | If two trees share an edge, \(E(\mathcal{T})\) lists it once. |
| \((e_0, \dots, e_n)\) | "an exchange chain" | A recorded cascade of possible tree swaps that frees the starting edge \(e_0\); the last edge \(e_n\) lies on no tree of the family. | A single edge outside all trees is an exchange chain of length 0. |
| \(\mathrm{ter}(\mathcal{P})\) | "the terminal vertices of P" | For a set \(\mathcal{P}\) of directed paths, the set of their last vertices. | For a path ending at \(y\) plus the lone vertex \(z\): \(\mathrm{ter} = \{y, z\}\). |
| \((P, \le)\) | "a partially ordered set" | A set \(P\) with an order in which some pairs are comparable and others are not. | Numbers under divisibility: 2 divides 6, but 4 and 6 are incomparable. |
Chapter 3: Connectivity
18 new symbols (2 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(G \mathbin{\dot{-}} e\) | "G delete-and-suppress e" | Delete the edge \(e\), then erase any end of \(e\) left with exactly two edges, fusing that vertex's two edges into a single edge. | Applied to the right edge of \(K_{3,3}\) it gives \(K^4\) (Figure 3.5). |
| \(k(G, A, B)\) | "the separator number of A and B" | The fewest vertices whose deletion destroys every path from the vertex set \(A\) to the vertex set \(B\). The deleted vertices are allowed to lie in \(A\) or \(B\). | If \(G\) has no edges, \(k(G,A,B) = |A \cap B|\). |
| \(\mathcal{P}, \mathcal{Q}\) | "the path system P" | A script letter naming a set of paths, here always a set of pairwise disjoint \(A\)–\(B\) paths. | \(\mathcal{P} = \{P_1, P_2\}\): two disjoint routes. |
| \(V[\mathcal{P}]\) | "the vertices of the system P" | Every vertex lying on some path of \(\mathcal{P}\), collected into one set. | For \(\mathcal{P} = \{abc,\; de\}\): \(V[\mathcal{P}] = \{a,b,c,d,e\}\). |
| \(E[\mathcal{P}]\) | "the edges of the system P" | Every edge used by some path of \(\mathcal{P}\). | Same system: \(E[\mathcal{P}] = \{ab, bc, de\}\). |
| \(C^n * K^1\) | "the wheel with an n-rim" | A cycle on \(n\) vertices (the rim) plus one extra vertex (the hub) joined to every rim vertex. | \(C^3 * K^1 = K^4\), the smallest wheel. |
| \(A\)-path | "an A-path" | A path with at least one edge whose two ends lie in the set \(A\) and none of whose interior vertices lies in \(A\). | In a triangle with \(A\) all three vertices, each of the 3 edges is an \(A\)-path. |
| \(H\)-path | "an H-path" | For a subgraph \(H\): a path that touches \(H\) exactly in its two end vertices and is not itself an edge of \(H\). | A detour that leaves \(H\), travels outside, and comes back. |
| \(\kappa_H(G)\) | "kappa sub H of G" | The fewest vertices, all taken outside \(H\), that between them meet every \(H\)-path. | If every \(H\)-path runs through one of two hubs, \(\kappa_H(G) \le 2\). |
| \(\lambda_H(G)\) | "lambda sub H of G" | The fewest edges that between them meet every \(H\)-path. | If every \(H\)-path crosses one bridge, \(\lambda_H(G) = 1\). |
| \(\partial C\) | "the boundary of C" | Those vertices of a piece \(C\) that still send an edge out to the world beyond \(C\). | If \(C\) is the single edge \(uv\) and only \(u\) looks outward, \(\partial C = \{u\}\). |
| \(M_H(G)\) | "Mader's bound" | The cheapest score of a mixed blockade of the \(H\)-paths: the number of blocking vertices, plus \(\lfloor \frac{1}{2}|\partial C|\rfloor\) for each cluster \(C\) of blocking edges. | If 3 vertices alone block everything and nothing scores lower, \(M_H(G) = 3\). |
| \(\|U\|^+\) | "the outward edge count of U" | How many edges have at least one end in the vertex set \(U\). Edges leaving \(U\) are counted. | A single vertex \(u\) of degree 5 gives \(\|\{u\}\|^+ = 5\). |
| \(\kappa(G)\), \(\lambda(G)\) | "the connectivity", "the edge-connectivity" | (Chapter 1.) The largest \(k\) for which \(G\) is \(k\)-connected, respectively \(k\)-edge-connected. | \(\kappa(K^4) = 3\). |
| \(\delta(G)\), \(d(G)\), \(\varepsilon(G)\) | "min degree", "average degree", "edge density" | (Chapter 1.) Smallest number of edges at a vertex; average number; and \(\varepsilon(G) = \|G\|/|G|\), edges per vertex. Always \(d(G) = 2\varepsilon(G)\). | \(K^4\): \(\delta = 3\), \(d = 3\), \(\varepsilon = 6/4 = 1.5\). |
| \(G/e\) | "G contract e" | (Chapter 1.) Merge the two ends of the edge \(e\) into a single vertex, which inherits all their other neighbours. | Contracting any edge of \(K^4\) leaves a triangle. |
| \(TK^r\) | "a subdivision of K r" | (Chapter 1.) A copy of \(K^r\) with each edge stretched into a path. The \(r\) original vertices are its branch vertices. | \(K_{3,3}\) contains a \(TK^4\) (Figure 3.5, read backwards). |
| \(A\)–\(B\) path | "an A to B path" | (Chapter 1.) A path whose first vertex is its only vertex in \(A\) and whose last vertex is its only vertex in \(B\). | A single vertex lying in both \(A\) and \(B\) counts as an \(A\)–\(B\) path of length 0. |
Chapter 4: Planar Graphs
9 new symbols (2 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(F(G)\) | "the faces of G" | The set of faces of a plane graph \(G\): the connected regions the drawing cuts the plane into, the unbounded outer region included. | A drawn triangle has \(|F(G)| = 2\): inside and outside. |
| \(\ell\) | "ell, the face count" | \(\ell = |F(G)|\), the number of faces; used alongside \(n = |V|\) and \(m = |E|\) in Euler's formula. | For the drawn cube: \(n=8\), \(m=12\), \(\ell=6\). |
| \(G[f]\) | "the boundary of f" | The subgraph of \(G\) whose points form the frontier of the face \(f\): what you touch walking the rim of \(f\). (Same brackets as induced subgraphs \(G[U]\); the argument tells you which is meant.) | In a square with one diagonal, each triangular face has a triangle as its boundary. |
| \(\mathring{e}\), \(\mathring{P}\) | "the interior of e" | An edge (or arc) with its two endpoints removed: just the open middle part. | If \(P\) runs from \(x\) to \(y\), then \(\mathring{P} = P \setminus \{x,y\}\). |
| \(S^2\) | "the sphere" | The surface of a ball. Drawings transfer between the plane and the sphere, where the outer face loses its special status. | Puncture a sphere-drawing inside any face; that face becomes the outer one. |
| \(K_{3,3}\) | "K three three" (reminder) | The complete bipartite graph: two groups of three vertices, all nine cross edges, none inside a group. | The houses-and-utilities graph. |
| \(G^*\) | "G star, the dual of G" | The plane dual: one new vertex inside each face of \(G\), one new edge crossing each edge of \(G\). | The dual of the drawn cube is the octahedron. |
| \(e^*\) | "e star, the dual edge" | The edge of \(G^*\) that crosses \(e\), joining the dual vertices of the two faces on either side of \(e\); a loop if both sides are the same face. | A bridge in \(G\) dualizes to a loop in \(G^*\). |
| \(v^*(f)\), \(f^*(v)\) | "the dual vertex of f", "the dual face of v" | The vertex of \(G^*\) placed inside face \(f\); the face of \(G^*\) containing vertex \(v\). Two bijections that make duality tight. | The outer face of a drawn triangle contributes one dual vertex outside the triangle. |
Chapter 5: Colouring
10 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(c\colon V \to S\) | "a colouring c from V to S" | A rule assigning each vertex \(v\) a colour \(c(v)\) from a set \(S\), with adjacent vertices always coloured differently. | On a triangle \(abc\): \(c(a)=1\), \(c(b)=2\), \(c(c)=3\). |
| \(\chi(G)\) | "chi of G" | The chromatic number: the smallest number of colours that can properly colour the vertices of \(G\). | \(\chi(\text{triangle})=3\); \(\chi(\text{square})=2\). |
| \(\chi'(G)\) | "chi-prime of G" | The chromatic index: the smallest number of colours for the edges, where edges sharing an endpoint must differ. | \(\chi'(\text{triangle})=3\). |
| \(\mathrm{col}(G)\) | "the colouring number of G" | The least \(k\) such that the vertices can be listed in an order where each vertex has fewer than \(k\) neighbours earlier in the list. | Trees: \(\mathrm{col}=2\). |
| \((S_v)_{v \in V}\) | "the family of lists S-sub-v" | An assignment to each vertex \(v\) of its own personal menu \(S_v\) of permitted colours. | \(S_a=\{\text{red},\text{blue}\}\), \(S_b=\{\text{blue},\text{green}\}\). |
| \(\mathrm{ch}(G)\) | "the choice number of G" | The least \(k\) such that \(G\) can be coloured from the lists no matter which size-\(k\) menus are dealt. | \(\mathrm{ch}(K_{2,4})=3\) although \(\chi(K_{2,4})=2\). |
| \(\mathrm{ch}'(G)\) | "the list-chromatic index of G" | The edge version of the choice number: least \(k\) so that edges can always be coloured from any size-\(k\) menus. | Bipartite graphs: \(\mathrm{ch}'=\Delta\). |
| \(N^+(v)\), \(d^+(v)\) | "out-neighbourhood, out-degree of v" | In a directed graph: the set of vertices \(v\) points to, and how many there are. | In \(a \to b \to c \to a\): \(N^+(a)=\{b\}\), \(d^+(a)=1\). |
| \(\omega(G)\) | "omega of G" | The clique number: the size of the largest set of vertices that are all pairwise joined. | \(\omega(C^5)=2\): its biggest clique is a single edge. |
| \(\alpha(G)\) | "alpha of G" | The independence number: the size of the largest set of vertices with no edges among them. | \(\alpha(C^5)=2\). |
Chapter 6: Flows
18 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \((e,x,y)\) | "edge \(e\), travelled from \(x\) to \(y\)" | An oriented edge: the edge \(e=xy\) bundled with one of its two travel directions. A non-loop edge has two orientations; a loop has one. | If \(e\) joins \(a\) and \(b\), its orientations are \((e,a,b)\) and \((e,b,a)\). |
| \(\vec{e}\), \(\overleftarrow{e}\) | "\(e\) one way; \(e\) the reverse way" | Names for the two orientations of an edge \(e\); \(\overleftarrow{e}\) is whichever direction \(\vec{e}\) is not. | If \(\vec{e}=(e,a,b)\) then \(\overleftarrow{e}=(e,b,a)\). |
| \(\vec{E}\) | "the oriented edges of \(G\)" | Every edge of \(G\) listed once per direction. | A graph with 3 edges and no loops has 6 oriented edges. |
| \(\overline{X}\) | "\(X\) bar" | The complement of a vertex set: \(\overline{X}=V\setminus X\), all vertices not in \(X\). | If \(V=\{a,b,c,d\}\) and \(X=\{a,b\}\), then \(\overline{X}=\{c,d\}\). |
| \(\vec{F}(X,Y)\) | "the oriented edges in \(\vec{F}\) from \(X\) to \(Y\)" | The members of a set \(\vec{F}\) of oriented edges that start in \(X\) and end in \(Y\). Loops never count. | \(\vec{E}(x,V)\), also written \(\vec{E}(x)\): every direction leaving the vertex \(x\). |
| \(f(X,Y)\) | "the total flow from \(X\) to \(Y\)" | The sum of \(f\) over all oriented edges from \(X\) to \(Y\). | \(f(v,V)\) is the net amount leaving vertex \(v\). |
| (F1) | "antisymmetry" | \(f(e,x,y)=-f(e,y,x)\): reversing your point of view flips the sign. | "3 units from \(a\) to \(b\)" equals "\(-3\) units from \(b\) to \(a\)". |
| (F2) | "Kirchhoff's law" | \(f(v,V)=0\) at every vertex: in equals out everywhere. | One unit in, one unit out: balanced. |
| \(N=(G,s,t,c)\) | "a network" | A multigraph \(G\) with a source \(s\), a sink \(t\), and a capacity \(c(\vec{e})\) for each oriented edge. | Figure 6.3 shows a network on four vertices. |
| (F2′), (F3) | "balance except at \(s,t\); capacity limit" | (F2′): \(f(v,V)=0\) for every \(v\) other than \(s\) and \(t\). (F3): \(f(\vec{e})\le c(\vec{e})\) on every oriented edge. | A flow of 5 through a pipe of capacity 3 violates (F3). |
| \(|f|\) | "the total value of \(f\)" | The net flow across any source-side/sink-side frontier; the same number for every frontier, and equal to \(f(s,V)\). | The flow of Figure 6.3 has \(|f|=4\). |
| \(H\) | "the value group" | The number system flow values live in: any set with an addition that is commutative, has a zero, and has negatives (an "abelian group"). | The integers \(\mathbb{Z}\); the clock arithmetics \(\mathbb{Z}_k\). |
| \(\mathbb{Z}_k\) | "the integers modulo \(k\)" | Clock arithmetic with \(k\) positions \(0,1,\dots,k-1\); sums wrap around. | In \(\mathbb{Z}_3\): \(2+2=1\). |
| \(\mathbb{Z}_m\times\mathbb{Z}_n\) | "\(\mathbb{Z}_m\) cross \(\mathbb{Z}_n\)" | Pairs \((a,b)\), added coordinate by coordinate. It has \(m\cdot n\) elements. | In \(\mathbb{Z}_2\times\mathbb{Z}_3\): \((1,2)+(1,2)=(0,1)\). |
| \(\varphi(G)\) | "the flow number of \(G\)" | The least \(k\) such that \(G\) has a k-flow; \(\infty\) if there is none. | \(\varphi(K^4)=4\). |
| \(\sigma_k\) | "sigma \(k\)" | The remainder map from \(\mathbb{Z}\) to \(\mathbb{Z}_k\): each integer goes to its remainder modulo \(k\). | \(\sigma_3(5)=\bar{2}\). |
| \(\vec{C}\), \(\vec{P}\) | "\(C\) (or \(P\)) with an orientation" | A cycle, or a path, with a chosen direction of travel, recorded edge by edge. | The triangle \(abc\) travelled \(a\to b\to c\to a\). |
| \(F^*\), \(\vec{e}^{\,*}\) | "\(F\) star; \(e\) star" | For a plane graph and its dual: the dual edges of the edges in \(F\); and the oriented dual edge of \(\vec{e}\), obtained by rotating \(\vec{e}\) clockwise onto its dual edge. | Each side of a square corresponds to the dual edge crossing it. |
Chapter 7: Extremal Graph Theory
21 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\mathrm{ex}(n, H)\) | "the extremal number of H at n" | The largest number of edges an \(n\)-vertex graph can have while containing no copy of \(H\) as a subgraph. | \(\mathrm{ex}(5, K^3) = 6\): six edges dodge a triangle on 5 vertices, seven cannot. |
| \(T^{r-1}(n)\) | "the Turán graph" | Split \(n\) vertices into \(r-1\) teams of nearly equal size and join every pair from different teams. | \(T^3(8)\) has teams of sizes 3, 3, 2. |
| \(t_{r-1}(n)\) | "the Turán edge count" | The number of edges of \(T^{r-1}(n)\). | \(t_3(8) = 3{\cdot}3 + 3{\cdot}2 + 3{\cdot}2 = 21\). |
| \(K^r\) | "the complete graph on r vertices" | (From Chapter 1.) Every pair joined. Diestel writes \(K^r\) where many books write \(K_r\); this course follows Diestel. | \(K^3\) is a triangle, \(K^4\) has 4 vertices and 6 edges. |
| \(K_{r,s}\) | "complete bipartite" | (From Chapter 1.) Two sides of sizes \(r\) and \(s\), every cross pair joined, nothing inside a side. | \(K_{2,3}\) has 6 edges and no triangle. |
| \(K^r_s\) | "the blown-up clique" | The complete \(r\)-partite graph with \(s\) vertices in every part. \(K^r_1 = K^r\). | \(K^3_2\) is the octahedron: 6 vertices, 12 edges, 8 triangles. |
| \(\lVert X, Y \rVert\) | "the number of X-to-Y edges" | For disjoint vertex sets \(X\) and \(Y\), how many edges have one end in each. | In \(K_{2,3}\) with sides \(X, Y\): \(\lVert X, Y\rVert = 6\). |
| \(d(X, Y)\) | "the density of the pair X, Y" | \(\lVert X, Y\rVert / (|X|\,|Y|)\): the fraction of the possible cross edges that are present, a number between 0 and 1. | \(|X| = |Y| = 10\) with 40 cross edges gives \(d(X,Y) = 0.4\). |
| \(\epsilon\)-regular pair | "epsilon-regular" | A pair of sets in which every reasonably large window has about the same density as the whole pair. | A random bipartite graph is \(\epsilon\)-regular for small \(\epsilon\), with high probability. |
| \(\{V_0, V_1, \dots, V_k\}\) | "an epsilon-regular partition" | Equal chunks \(V_1, \dots, V_k\) plus a small leftover bin \(V_0\), such that all but a few chunk pairs are \(\epsilon\)-regular. | The output the regularity lemma guarantees. |
| \(V_0\) | "the exceptional set" | The leftover bin of the partition, small and ignored when regularity is judged. It exists so the other parts can be exactly equal in size. | With \(n = 103\) and \(k = 10\) parts of size 10, \(V_0\) holds 3 vertices. |
| \(R\) | "the regularity graph" | The small summary graph: one vertex per chunk, joined when the chunk pair is \(\epsilon\)-regular and has density at least \(d\). | If only the pairs among \(V_1, V_2, V_3\) qualify, \(R\) is a triangle. |
| \(R_s\) | "R blown up by s" | Replace each vertex of \(R\) by \(s\) copies and each edge by all \(s^2\) cross edges. | For \(R = K^3\) and \(s = 2\), \(R_s = K^3_2\). |
| \(\hom(H, G)\) | "the homomorphism count" | How many maps from the vertices of \(H\) to the vertices of \(G\) send every edge of \(H\) to an edge of \(G\). Non-adjacent vertices may collapse together. | \(\hom(K^2, G) = 2\lVert G\rVert\): each edge counted in both directions. |
| \(r_k(n)\) | "r-k of n" | The largest size of a subset of \(\{0, 1, \dots, n-1\}\) containing no \(k\) evenly spaced numbers. | \(r_3(5) = 4\): the set \(\{0,1,3,4\}\) has no three evenly spaced members. |
| \(K(x, d)\) | "the defining triangle" | In the proof about arithmetic progressions: the triangle on the three vertices \(x\), \(x+d\) and \(2x+d\), one for each starting number \(x\) and each gap \(d\). | \(K(2,1)\) is the triangle on 2, 3 and 5. |
| upper density | "positive upper density" | A set \(A\) of whole numbers keeps at least a fixed share \(\delta\) of \(\{0, \dots, n-1\}\) for infinitely many \(n\). | The even numbers have upper density \(1/2\). |
| \(W\) | "the Wagner graph" | Eight vertices in a ring, each also joined to the vertex opposite. 12 edges, needs 3 colours, has no \(K^5\) minor. | Figure 7.8. |
| \(H \preccurlyeq G\) | "H is a minor of G" | (From Chapter 1.) \(H\) appears after deleting parts of \(G\) and contracting connected chunks. | Contracting the five spokes of the Petersen graph gives \(K^5\). |
| \(TH \subseteq G\) | "G contains a subdivided H" | (From Chapter 1.) A copy of \(H\) whose edges have been stretched into internally disjoint paths. | Any cycle is a \(TK^3\). |
| \(d(G),\ \delta(G),\ g(G)\) | "average degree, minimum degree, girth" | (From Chapter 1.) Average number of edges at a vertex; smallest such number; length of the shortest cycle. | For the Petersen graph: \(d = \delta = 3\) and \(g = 5\). |
Chapter 8: Infinite Graphs
13 new symbols (5 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\aleph_0\) | "aleph-nought" | The smallest infinite cardinal: the size of \(\mathbb{N}\); "countably infinite." | The ray has \(\aleph_0\) vertices. |
| \(K^{\aleph_0}\) | "K aleph-nought" | The complete graph on countably infinitely many vertices. | Any two of its vertices are adjacent. |
| \(\omega\) | "an end omega" | An end: an equivalence class of rays that no finite vertex deletion can separate. | All rays of the infinite grid form one end. |
| \(\Omega(G)\) | "the ends of G" | The set of all ends of \(G\); one also writes \(G = (V, E, \Omega)\). | For the double ray, \(|\Omega| = 2\). |
| \(T_2\) | "the binary tree" | The rooted tree whose vertices are the finite 0–1 strings; each string \(s\) has upper neighbours \(s0\) and \(s1\). | Vertex \(01\) has upper neighbours \(010\) and \(011\). |
| \(H^\infty\) | "the hexagonal quarter grid" | A brick-wall-patterned subgraph of the infinite grid; every vertex has degree at most 3. | Halin's grid theorem finds a \(TH^\infty\) in any graph with a thick end. |
| \(nH\), \(\aleph_0 H\) | "n copies of H" | The disjoint union of \(n\), respectively countably many, copies of \(H\). | \(3K^3\) is three disjoint triangles. |
| \((\ast)\) | "the extension property" | For any disjoint finite vertex sets \(U, W\) some vertex is adjacent to all of \(U\) and none of \(W\). | Used back-and-forth to prove \(R\) unique. |
| \(\mathring e\), \(\overline X\) | "the interior of e; the closure of X" | \(\mathring e\): the inside of edge \(e\), without its endpoints; \(\overline X\): the point set \(X\) plus all points it approaches in \(|G|\). | \(\overline V = V \cup \Omega\). |
| arc, circle, circuit | — | Arc: a topological copy of the segment \([0,1]\) inside \(|G|\); circle: a topological copy of the round circle; circuit: the edge set of a circle. | A double ray plus its two distinct ends is an arc. |
| \(\mathcal{C}_{\text{fin}}(G)\) | "the finitary cycle space" | Finite sums of finite circuits, as in Chapter 1. | \(\mathcal{C}_{\text{fin}}(G) \subseteq \mathcal{C}(G)\), with equality iff \(G\) is finite. |
| \(G/p\) | "G contracted by p" | The finite multigraph obtained by collapsing each class of a finite vertex partition \(p\) to a single vertex. | Collapsing all of \(G\) minus a finite set, component by component. |
| \(\|G\| = \varprojlim |G/p|\) | "the inverse limit" | The space of all consistent choices of one point in every finite view \(|G/p|\). Not the size of \(G\) in this chapter. | Theorem: \(\|G\| \cong |G|\) for connected locally finite \(G\). |
Chapter 9: Ramsey Theory
18 new symbols (5 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \([X]^k\) | "the k-subsets of X" | All subsets of the set \(X\) that have exactly \(k\) elements. Nothing else. | \(X=\{a,b,c\}\): \([X]^2=\{\{a,b\},\{a,c\},\{b,c\}\}\). |
| \(c\)-colouring | "a c-colouring" | Any way of sorting things into \(c\) labelled groups called colours. No rule of any kind. Groups may be empty. | Painting each edge of a graph violet or gold is a 2-colouring of its edge set. |
| monochromatic | "one-coloured" | A set \(Y\) is monochromatic when every \(k\)-subset of \(Y\) got the same colour. A subgraph is monochromatic when all its edges did. | In a violet/gold painting of \(K^6\), a triangle with three violet edges. |
| \(R(r)\) | "the Ramsey number of r" | The smallest \(n\) such that every graph on at least \(n\) vertices has \(r\) pairwise adjacent vertices or \(r\) pairwise non-adjacent ones. | \(R(3)=6\): the party puzzle. |
| \(R(k,c,r)\) | "the general Ramsey number" | The smallest \(n\) such that any \(c\)-colouring of the \(k\)-subsets of an \(n\)-set leaves some \(r\)-subset monochromatic. | \(R(2,2,3)=6\) is the party puzzle again. |
| \(R(H)\) | "the Ramsey number of H" | The smallest \(n\) such that every graph \(G\) on \(n\) vertices contains \(H\), or the complement \(\overline{G}\) does. | \(R(K^3)=R(3)=6\). |
| \(R(H_1,H_2)\) | "the Ramsey number of H1 against H2" | Same idea with two different targets: \(H_1\) inside \(G\), or \(H_2\) inside \(\overline{G}\). | \(R(T,K^3)=7\) for any 4-vertex tree \(T\). |
| \((V_1,V_2,E)\) | "a bipartite graph with its sides named" | A bipartite graph recorded together with which side is which, so that copies cannot swap the sides. | Points on top, blocks underneath, edges only between the two. |
| \(\varphi \colon P \to P'\) | "phi embeds P into P-prime" | A no-collisions map of vertices that keeps sides fixed and sends edges to edges and non-edges to non-edges. | Placing a 4-cycle inside a bigger bipartite graph without picking up an extra chord. |
| \((X,[X]^k,E)\) | "the point-block graph" | A bipartite graph whose first side is a set of points, whose second side is all \(k\)-element blocks of points, joined when the point belongs to the block. | \(X=\{1,2,3\}\), \(k=2\): point 1 joins blocks \(\{1,2\}\) and \(\{1,3\}\). |
| \(*\) | "join" | (Chapter 1.) Put two graphs side by side and add every possible edge between them. | A wheel is \(C^{n-1} * K^1\): a cycle plus a hub wired to all of it. |
| \(C^n * \overline{K^2}\) | "a double wheel" | A cycle plus two hubs, each wired to every cycle vertex, the two hubs not wired to each other. | \(C^4 * \overline{K^2}\) is the octahedron. |
| \(\mathcal{P} \le \mathcal{P}'\) | "P fits inside P-prime" | Two families of graphs, compared: every graph in \(\mathcal{P}\) sits inside some graph in \(\mathcal{P}'\), under whichever containment relation is in force. | All paths \(\le\) all subdivided stars: a path is a two-armed star. |
| \(\mathcal{P} \sim \mathcal{P}'\) | "P and P-prime are equivalent" | Both \(\mathcal{P}\le\mathcal{P}'\) and \(\mathcal{P}'\le\mathcal{P}\). Interchangeable for everything in this chapter. | All paths \(\sim\) all even-length paths. |
| \(K_{m,n}\) | "the complete bipartite graph" | (Chapter 1.) An \(m\)-group and an \(n\)-group, every cross pair joined, no pair inside a group. \(K_{1,r}\) is the star: one hub, \(r\) pairwise non-adjacent leaves. | \(K_{2,3}\) has two poles sharing three common neighbours. |
| \(P^r\) | "the path of length r" | (Chapter 1.) \(r\) edges in a row, so \(r+1\) vertices. Diestel indexes paths by edges, not vertices. | \(P^2\) has three vertices and two edges. |
| \(C^r\) | "the cycle of length r" | (Chapter 1.) \(r\) vertices in a ring joined by \(r\) edges. | \(C^5\) is the pentagon. |
| \(\Delta(H)\) | "the maximum degree of H" | (Chapter 1.) The largest number of neighbours any single vertex of \(H\) has. | A path has \(\Delta = 2\); a star \(K_{1,6}\) has \(\Delta = 6\). |
Chapter 10: Hamilton Cycles
8 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(G^d\) | "the d-th power of G" | Same vertices as \(G\); an edge joins two vertices whenever they are at distance at most \(d\) in \(G\) (reachable in at most \(d\) steps). | If \(G\) is the path \(a\,b\,c\,d\), then \(G^2\) adds \(ac\) and \(bd\), but not \(ad\) (distance 3). |
| \(G^2\) | "the square of G" | The case \(d=2\): keep all edges of \(G\), add an edge between every pair of vertices exactly two steps apart. | The square of the path \(v_1 v_2 v_3 v_4 v_5\) adds \(v_1v_3\), \(v_2v_4\), \(v_3v_5\). |
| \((d_1, \dots, d_n)\) | "the degree sequence" | All \(n\) vertex degrees of a graph, sorted in increasing order: \(d_1 \le d_2 \le \dots \le d_n\). | Two triangles sharing a vertex (the bowtie): \((2,2,2,2,4)\). |
| \(v^+\) | "the successor of v" | Fix a direction of travel around a cycle; \(v^+\) is the vertex that comes right after \(v\). | On the cycle \(v_1 v_2 v_3 v_1\), travelling in index order, \(v_1^+ = v_2\). |
| \(V^+\) | "V plus" | The set of successors of all vertices in a set \(V\): \(V^+ = \{v^+ : v \in V\}\). | On that same triangle, \(\{v_1, v_2\}^+ = \{v_2, v_3\}\). |
| \(t\)-tough | "t tough" | Deleting any separating set \(S\) of vertices leaves at most \(|S|/t\) connected pieces. Larger \(t\) means harder to shatter. | A cycle is 1-tough: deleting \(k\) vertices leaves at most \(k\) arcs. |
| \(G * K^1\) | "G joined with K one" | Add one new vertex to \(G\) and connect it to every vertex of \(G\). | A Hamilton path in \(G\) becomes a Hamilton cycle in \(G * K^1\), closed through the new vertex. |
| \(\|X, Y\|\) | "the number of X–Y edges" | The count of edges with one end in \(X\) and the other in \(Y\). | In \(K_{2,3}\) with classes \(X\) and \(Y\): \(\|X,Y\| = 6\). |
Chapter 11: Random Graphs
18 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\mathcal{G}(n,p)\) | "the random graph model on n vertices with edge probability p" | The probability space of all graphs on a fixed set of \(n\) labelled vertices, where each possible edge is present with probability \(p\), independently of all others. | In \(\mathcal{G}(3,\tfrac12)\) the triangle occurs with probability \(\tfrac18\). |
| \(p\) | "the edge probability" | The chance that any one potential edge is accepted. Either a constant or a function \(p = p(n)\) of the number of vertices. | \(p=\tfrac12\), or \(p(n)=1/n\). |
| \(q\) | "q, the non-edge probability" | \(q := 1-p\), the chance that a potential edge is rejected. | If \(p=0.3\) then \(q=0.7\). |
| \(P[\dots]\) | "the probability that …" | The probability of the event described inside the brackets. An event is a set of graphs, viewed as a yes/no question about the random graph. | \(P[H \subseteq G]\) is the probability that a fixed \(H\) is a subgraph of \(G\). |
| \(X\) | "a random variable" | Any function assigning a non-negative number to each graph. Counts and graph invariants all qualify. | \(X(G)=\) number of triangles in \(G\). |
| \(E(X)\) | "the expectation of X" | The probability-weighted average of \(X\) over all graphs: \(E(X) = \sum_G P(\{G\})\, X(G)\). | Expected number of edges in \(\mathcal{G}(n,p)\): \(\binom{n}{2}p\). |
| \(X_C\) | "the indicator of C" | The 0/1 flag of one fixed graph \(C\): \(X_C(G)=1\) if \(C \subseteq G\), else \(0\). Its expectation equals a probability: \(E(X_C) = P[C \subseteq G]\). | Fixed triangle \(C\): \(E(X_C)=p^3\). |
| \((n)_k\) | "n falling k" | The falling factorial \(n(n-1)\cdots(n-k+1)\): the number of ordered sequences of \(k\) distinct vertices chosen from \(n\). | \((5)_3 = 5\cdot4\cdot3 = 60\). |
| almost all | "almost all / almost surely / almost no" | A property holds for almost all \(G \in \mathcal{G}(n,p)\) if \(P[G \in \mathcal{P}] \to 1\) as \(n \to \infty\); almost no graph has it if the probability tends to \(0\). | For constant \(p\), almost every graph is connected. |
| \(\mathcal{P}\) | "a graph property" | A class of graphs closed under isomorphism: membership depends only on the shape, never on vertex labels. | "Contains a triangle" is a property; "vertex 3 has degree 5" is not. |
| \(\mathcal{P}_{i,j}\) | "the extension property with parameters i and j" | Every "wish list" of at most \(i\) wanted neighbours and at most \(j\) forbidden ones is granted by some vertex adjacent to all of the first group and none of the second. | \(\mathcal{P}_{1,1}\): any two vertices \(u,w\) have some \(v\) joined to \(u\) but not to \(w\). |
| \(t(n)\) | "a threshold function" | A tipping point for a property: if \(p/t \to 0\) the property almost surely fails; if \(p/t \to \infty\) it almost surely holds. | \(t(n)=1/n\) for "contains a triangle". |
| \(\mu\) | "mu, the mean" | Shorthand for \(E(X)\); in this chapter usually a function of \(n\). | For triangle counts, \(\mu = \binom{n}{3}p^3\). |
| \(\sigma^2\) | "sigma squared, the variance" | \(\sigma^2 := E\big((X-\mu)^2\big)\), the average squared distance of \(X\) from its mean. Small \(\sigma^2\) means \(X\) is concentrated near \(\mu\). | If \(X\) is constant, \(\sigma^2 = 0\). |
| \(\varepsilon'(H)\) | "the maximum local edge density of H" | \(\varepsilon'(H) := \max\{\varepsilon(F) : F \subseteq H\}\): scan every subgraph of \(H\) and record the largest edges-per-vertex ratio \(\varepsilon(F) = \|F\|/|F|\). | \(K^4\) plus a pendant vertex: \(\varepsilon' = 6/4 = 1.5\). |
| balanced | "H is balanced" | \(\varepsilon'(H) = \varepsilon(H)\): no piece of \(H\) is denser than the whole. Cycles and trees are balanced. | \(\varepsilon'(C^5) = \varepsilon(C^5) = 1\). |
| \(\mathcal{G}(\aleph_0,p)\) | "the infinite random graph model" | The same coin-flip construction on the countably infinite vertex set \(\mathbb{N}\); \(\aleph_0\), "aleph-nought", is the size of \(\mathbb{N}\). Here "almost surely" means literally with probability 1. | Almost surely isomorphic to the Rado graph. |
| \(G(n,M)\) | "the uniform random graph model" | Pick one graph uniformly at random among all graphs on \(n\) labelled vertices with exactly \(M\) edges. | Behaves like \(\mathcal{G}(n,p)\) when \(M \approx p\binom{n}{2}\). |
Chapter 12: Graph Minors, Tree-Width and Tangles
14 new symbols (3 rows here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\le\) | "fits below" | A quasi-ordering: a comparison that is reflexive (\(x \le x\)) and transitive (\(x \le y\) and \(y \le z\) give \(x \le z\)); some pairs may be incomparable. | "is a minor of" on graphs. |
| \((x_i, x_j)\), \(i < j\), \(x_i \le x_j\) | "a good pair" | In an infinite sequence, an earlier term that fits below a later term. A sequence with a good pair is good; with none, bad. | In \(P^3, P^1, P^2, P^4, \dots\) (paths by length), \((P^1, P^2)\) is a good pair. |
| \([X]^{<\omega}\) | "finite subsets of X" | The collection of all finite subsets of a set \(X\). | \(\{2,5\}\) is one element of \([\mathbb{N}]^{<\omega}\). |
| \((T, \mathcal V)\), bags \(V_t\) | "a tree-decomposition" | A tree \(T\) plus one bag \(V_t\) of vertices of \(G\) per tree node \(t\), obeying axioms (T1)–(T3) below. | Path \(a\)–\(b\)–\(c\): tree \(t_1\)–\(t_2\), bags \(\{a,b\}, \{b,c\}\). |
| \(V_{t_1} \cap V_{t_2}\) | "the adhesion set" | The overlap of two neighbouring bags; it separates the two sides of the decomposition. The largest such overlap is the decomposition's adhesion. | Above: adhesion set \(\{b\}\), adhesion 1. |
| \(\mathrm{tw}(G)\) | "the tree-width of G" | The smallest possible width of a tree-decomposition of \(G\); width means largest bag size minus one. | \(\mathrm{tw}(\text{tree}) = 1\); \(\mathrm{tw}(K^n) = n-1\). |
| \(\mathrm{ctw}(G)\) | "the connected tree-width" | Least width over tree-decompositions all of whose parts are connected subgraphs. | For the 10-vertex cycle: \(\mathrm{tw} = 2\) but \(\mathrm{ctw} = 5\). |
| \(\{A, B\}\), \(|A \cap B|\) | "a separation and its order" | (Separations from Chapter 3.) \(A \cup B\) is all of \(V(G)\) and no edge jumps between \(A \setminus B\) and \(B \setminus A\); the order is the size of the overlap. | In path \(a\)–\(b\)–\(c\): \(\{\{a,b\},\{b,c\}\}\) has order 1. |
| \((A, B)\) | "the separation pointed at B" | An oriented separation: \(\{A,B\}\) with \(B\) declared the important side. \((A,B) \ge (C,D)\) means \(A \subseteq C\) and \(B \supseteq D\): the first arrow points at least as far inward. | Each \(\{A,B\}\) has two orientations, \((A,B)\) and \((B,A)\). |
| \(S_k\) | "the low-order separations" | All separations of \(G\) of order less than \(k\). | \(S_3\) = all separations with overlap of size 0, 1 or 2. |
| \(\mathcal T\), \(\mathcal T^*\) | "the forbidden triples (and stars)" | \(\mathcal T\): all sets of at most three oriented separations whose small sides together cover \(G\). \(\mathcal T^*\): those that are stars (all pointing at each other). A tangle must avoid \(\mathcal T\). | One separation \((B, A)\) with \(G[B] = G\) already lies in \(\mathcal T\). |
| \(\mathrm{Forb}_{\preccurlyeq}(\mathcal H)\) | "graphs forbidding \(\mathcal H\) as minors" | The class of graphs having no member of \(\mathcal H\) as a minor. | \(\mathrm{Forb}_{\preccurlyeq}(K^3)\) = all forests. |
| \(\mathcal K_{\mathcal P}\) | "the Kuratowski set of \(\mathcal P\)" | The unique smallest forbidden-minor set for a minor-closed property \(\mathcal P\): the minor-minimal graphs outside \(\mathcal P\). | For planarity, \(\mathcal K_{\mathcal P} = \{K^5, K_{3,3}\}\). |
| \(H^r\) | "the hexagonal grid of radius r" | The honeycomb-shaped piece of the plane hexagonal lattice with \(r\) rings around a central face; \(S_k\) names its \(k\)-th perimeter cycle and \(R_k\) the ring between \(S_k\) and \(S_{k+1}\). | \(S_1\) is the central hexagon itself. |
Chapter 13: Graphs in Artificial Intelligence
6 new symbols (1 row here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(\mathbb{R}^d\) | "R d" | The set of lists of \(d\) real numbers. A vertex state is one such list, also called a vector. | \((0.2,\,-1.5)\) is a point of \(\mathbb{R}^2\). |
| \(h_v^{(k)}\) | "the state of \(v\) after round \(k\)" | The vector of numbers vertex \(v\) carries after \(k\) rounds of message passing; \(h_v^{(0)}\) is the input data. | In Figure 13.1, \(h_b^{(0)}=2\) and \(h_b^{(1)}=8\). |
| \(w_{uv}\) | "the weight from \(u\) to \(v\)" | A number attached to the ordered pair \((u,v)\); an edge weight that may differ from \(w_{vu}\). | In Figure 13.2, \(w_{\text{cat},\text{sat}}=0.6\). |
| \(D\) | "the degree matrix" | The diagonal matrix with the degree \(d(v)\) in position \((v,v)\) and zeros elsewhere. | For a triangle, the diagonal reads \(2,2,2\). |
| \(L\) | "the Laplacian" | \(L = D - A\): degree matrix minus adjacency matrix. | For a triangle: \(2\) on the diagonal, \(-1\) off it. |
| \(\lambda_2\) | "lambda two" | The second-smallest eigenvalue of \(L\) (in this chapter only; it is not the edge-connectivity \(\lambda(G)\)). | \(\lambda_2 > 0\) exactly when \(G\) is connected. |
Chapter 14: GraphRAG: Retrieval over Knowledge Graphs
5 new symbols (1 row here repeat symbols introduced earlier and are not listed again) · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \(w(uv)\) | "the weight of the edge \(uv\)" | A number attached to the edge between \(u\) and \(v\), here measuring how often and how strongly two entities are linked in the text. | If two entities co-occur in 3 chunks, \(w(uv)=3\). |
| \(Q(\mathcal{P})\) | "the modularity of \(\mathcal{P}\)" | A quality score for a partition: high when many edges lie inside parts and few run between them, relative to chance. | Two loose blobs joined by one edge: splitting at that edge gives high \(Q\). |
| \(G/\mathcal{P}\) | "\(G\) contracted by \(\mathcal{P}\)" | The aggregate graph: one vertex per community of \(\mathcal{P}\), with an edge between two of them when some edge of \(G\) runs between the two communities. Extends the edge contraction \(G/e\) of Chapter 1. | Contracting \(\{a,b,c\}\) and \(\{d,e\}\) gives a graph on 2 vertices. |
| \(\pi(v)\) | "the PageRank of \(v\)" | The long-run share of time a certain random walk spends at vertex \(v\); a score of how central \(v\) is. | A hub of high degree collects a large \(\pi(v)\). |
| \(\pi_S(v)\) | "the PageRank of \(v\) personalized to \(S\)" | The same walk, except the teleport step returns to the seed set \(S\); scores how reachable \(v\) is by short walks from \(S\). | With \(S=\{s\}\), the neighbours of \(s\) get large \(\pi_S\). |
Chapter 15: Trustworthy AI, One Graph at a Time
11 new symbols · go to the chapter
| Symbol | Read it as | Meaning | Tiny example |
|---|---|---|---|
| \((s, r, o)\) | "the triple s, r, o" | A fact stored as a directed edge from subject \(s\) to object \(o\), labeled with the relation \(r\). | (Canberra, capital_of, Australia). |
| \(d^+(v)\) | "the out-degree of v" | The number of edges leaving vertex \(v\) in a directed graph. | If \(v\) has edges to \(a\) and \(b\), then \(d^+(v)=2\). |
| \(d^-(v)\) | "the in-degree of v" | The number of edges entering vertex \(v\). | A merge vertex in a graph of thoughts has \(d^-(v)\ge 2\). |
| \(\mathrm{Anc}(v)\) | "the ancestors of v" | All vertices from which a directed path reaches \(v\). (Course-local shorthand, not in Diestel.) | In \(a \to b \to c\), \(\mathrm{Anc}(c)=\{a,b\}\). |
| \(\mathrm{Desc}(v)\) | "the descendants of v" | All vertices reachable from \(v\) by a directed path. (Course-local shorthand.) | In \(a \to b \to c\), \(\mathrm{Desc}(a)=\{b,c\}\). |
| \(X \to Y\) | "X points to Y"; in a causal graph, "X directly causes Y" | A directed edge from \(X\) to \(Y\). | Season \(\to\) Drownings. |
| \(X \perp Y \mid Z\) | "X is independent of Y given Z" | Once \(Z\) is held fixed, learning \(X\) tells you nothing further about \(Y\). | IceCream \(\perp\) Drownings \(\mid\) Season. |
| \(\mathrm{do}(X{=}x)\) | "do X equals x"; "set X to x by force" | An intervention: delete every edge into \(X\) and fix its value to \(x\). | \(\mathrm{do}(\text{IceCream}{=}0)\): ban ice cream. |
| \(a \le b\) | "a is below b" (partial order) | An order relation in which some pairs may be incomparable. | Public \(\le\) Secret; Read and Secrets incomparable. |
| \(a \vee b\) | "the join of a and b" | The least element above both \(a\) and \(b\) in a lattice. | Read \(\vee\) Secrets = Top. |
| \(a \wedge b\) | "the meet of a and b" | The greatest element below both \(a\) and \(b\) in a lattice. | Read \(\wedge\) Secrets = Public. |
Reading mathematics aloud
Three habits carry most of the load when a formula looks impenetrable.
Say it as a sentence. \(\delta(G) \ge 2\) is not a picture, it is the sentence "every vertex of \(G\) has at least two neighbours." Formulas are compressed English, and decompressing them is a skill that improves with deliberate practice.
Instantiate on something tiny. When a statement quantifies over all graphs, test it on a triangle, on a single edge, on a path with three vertices. A claim that survives those has earned a little trust; a claim that dies on one of them was misread or is false.
Track what varies and what is fixed. In \(\varepsilon(G) = \|G\| / |G|\), the graph varies and the operation is fixed. In \(R(k, \ell)\), the two numbers vary and the theorem promises the value exists. Most confusion in reading mathematics is confusion about which letters are free to move.
Chapter 0 teaches this vocabulary from nothing, and every later chapter opens with its own notation table before using a symbol.
Source
- R. Diestel, Graph Theory, 6th edition, Graduate Texts in Mathematics 173, Springer (2024). The book's own symbol index appears on pp. 453–456; this course follows its notation throughout, noting the few places where the wider literature differs. doi:10.1007/978-3-662-70107-2