Math 510
Introduction to Graph Theory
Spring 2026

Index

Terminology
Notation
Rules for 3-block decomposition
Plane duality.

Dictionary

There is a lot of variation in terminology and notation in graph theory. Here I'm trying to give you enough of it so when I forget Tutte's choices and use mine instead, or if you read other literature, you won't be confused. There is also some clarification of Tutte's usages.

Terminology

Order and size are widely used in graph theory to mean |V| and |E|, respectively. Tutte does not follow these conventions. I will sometimes do so.

Strict graph: It is generally known as a simple graph. Most graph theorists call it a "graph"; they tend to call our graphs "multigraphs" or (pardon the expression) "pseudographs".

Reduction G·S: Usually this is called an edge-induced subgraph.

Complement of a subgraph: This is different from the common concept of the complement of a (simple) graph.

Special sets, edges, vertices.
Special graphs, subgraphs.
- Star graph: It is a name for K_1,m.
- Clique: Tutte means what is usually called a complete graph. Usually, a clique is a set of pairwise adjacent vertices in a graph; note that it is a vertex set, not a graph, but that may be overlooked and a complete subgraph of a graph can be called a clique.
- Independent (or stable) vertex set: Any subset X of V such that no edge has both ends in X.
- Matching: A partial 1-factor, i.e., a set of pairwise nonadjacent edges.
  (Crazy graph theory terminology: Many people call a 1-factor a "matching" and a partial 1-factor a "partial matching". Many call a 1-factor a "perfect matching" and a partial 1-factor a "matching".) (!)
  The matching number of G is the largest size of a matching in G.
- Vertex cover: A set X of vertices such that every edge has at least one endpoint in X.
  The vertex cover number of G is the smallest size of a vertex cover in G.
- Circuit: Also known as a cycle (but Tutte means something different by that) and a circle (by me, and by König in the first graph theory textbook, in 1936).
  Worse, the word "circuit" is sometimes used in graph theory for other things.
- Bridge of H: A maximal piece of a graph that is separated by a subgraph H.
  Most graph theorists use this word for an isthmus, but I agree with Tutte. His "bridges" are bigger and better.
Walks, trails, arcs, and paths.
- Walk: A sequence of vertices and edges, v₀e₁v₁···e_l−1v_l (where the length l ≥ 0), such that for each i, v_i−1 and v_i are the vertices incident with e_i.
- Trail: A walk that has no repeated edges.
- k-Arc: Most people call this a path (of length k and order k+1). Note that Tutte has not assigned a direction to the arc, only to the labeling. Also, the k+1 vertices are distinct.
  (The word "arc" is often used for a directed edge, but Tutte calls it a "dart".)
- Distance: The distance between vertices x and y, dist(x,y), is the length of a shortest arc of which they are the endpoints. If there is no such arc, the distance is &infty;. For example, dist(x,x) = 0, and dist(x,y) = 1 if and only if x and y are adjacent.
Fundamental circuit: Let T be a spanning tree of G. The fundamental circuit of an edge A ∉ E(T), with respect to T, is the unique circuit in T ∪ A. My notation: C_T(A).
A decomposition of G is a representation of G as the union of edge-disjoint subgraphs, each of which has at least one edge. We are not concerned with the vertex sets of the subgraphs.
For example, one may want to decompose a graph into 2-arcs. There is a nice Theorem: A connected simple graph decomposes into 2-arcs if and only if |E| is even. The proof is not trivial.
Girth g(G): It is the shortest length of a circuit in G, but ∞ if there are no circuits.
Forbidden minors.
- Series-parallel graph: A graph that can be constructed by series or parallel connection of smaller series-parallel graphs, starting with a link or loop. These graphs have two distinguished vertices where the series and parallel connections must take place.
  Theorem. G is a series-parallel graph if and only if it has no K₄ minor.
- Planar graph: A graph that can be drawn in the plane without self-intersections.
  Kuratowski's Theorem. G is planar if and only if it has no K₅ or K_3,3 minor.
  Wagner's Theorem characterizes the graphs that have no K₅ minor; they are planar with limited attached graphs.
Forbidden induced subgraphs. (We normally assume the graph is simple. We write P_n for a path of order n, not length n.)
- Induced subgraph: Any graph obtained from G by deleting vertices.
- Threshold graph: A graph whose vertices can be ordered v₁, v₂, ..., v_n so that each v_i is either adjacent to all preceding vertices or nonadjacent to all of them.
  Theorem. G is a threshold graph if and only if it has no induced C₄, C₄^c, or P₄.
- Perfect graph: The definition, involving chromatic number, will come later.
  Strong Perfect Graph Theorem. G is perfect if and only if it has no induced C_m or ^{^{^__}}C_m for odd m ≥ 5. Here ^{^{^__}}C_m (I'm approximating a bar over the C) means the complement of the circuit graph, not as a subgraph of anything.
Algebra.
Polynomials.
- Tutte polynomial T_G(x,y) or T(G;x,y) = dichromate χ(G;x,y): Tutte's "dichromate" is known to the rest of the world as the Tutte polynomial. It has become very popular.
- Dichromate ≠ dichromatic polynomial Q(G;x,y): Don't confuse the Tutte polynomial T_G ("dichromate") with the dichromatic polynomial Q_G. The Tutte polynomial generalizes to matroids. The dichromatic polynomial, like the chromatic polynomial, is essentially graphic.
- Chromatic polynomial, χ_G(λ) or P(G;λ): For a positive integer k, χ_G(k) = the number of proper k-colorings of G.
- Flow polynomial, φ_G(λ) or F(G;λ): For a positive integer k, φ_G(k) = the number of nowhere-zero R-cycles of G, where R is a nice ring of order k, such as Z_k or a finite vector space F_q^d (q = prime power).
  It does not equal the number of nowhere-zero k-flows of G, which is not given by a polynomial.
- Whitney numbers (of the first kind): They are the coefficients of the chromatic polynomial of G: χ_G(λ) = ∑_i=0ⁿ w_i λ^n-i. The absolute values, (−1)ⁱw_i, count certain edge sets that I can't describe concisely.
Flow number φ(G): The smallest nonnegative integer m for which there exists a nowhere-zero (integral) m-flow, or equivalently (page 240) a nowhere-zero cycle in a ring R of order m such as Z_m.
Hint: Since the flow polynomial F_G(m) counts nowhere-zero R-cycles, the existence of such an R-cycle is equivalent to F_G(m) > 0. Use that fact.

Notation

Shorthand:

∴ means "therefore". LaTeX: \therefore. (This is a very old notation.)
∵ means "because". LaTeX: \because. (Also very old.)
⇒ means "implies", which is not a synonym of "therefore". LaTeX: \implies is one way to get it.

I is Tutte's notation for Z, the ring of integers.

Special graphs

K_n is the complete graph of order n. It is the simple graph in which every vertex is adjacent to every other.
K_r,s is the complete bipartite graph. It is the simple graph in which V = V₁ ∪ V₂ (disjoint union), with r vertices in V₁ and s in V₂, where every vertex of V₁ is adjacent to every vertex of V₂ and there are no other edges. See Tutte, p. 79.
W_n is the wheel with n+1 vertices. See Tutte, p. 78. (Tutte says "order n". This contradicts the common use of "order" to mean |V|. I will have to be careful.)

Graph operations

G[U] is standard notation for the induced subgraph on U ⊆ V. (I prefer G:U, which looks more like an operation on G similar to restriction of a function. But Tutte uses : for a different purpose.)
G·S, the reduction, or edge-induced subgraph. There is no standard notation. I would use G:S if Tutte hadn't already used : somewhere.
G × S, the contraction to S, is more usually written as G/(E ∖ S), the contraction of E ∖ S. That is, we think of contracting an edge set instead of contracting "to" an edge set.

The restriction f·S of a mapping f: E(G) → E(H) is what we normally write as f|_S. The same for a mapping of vertex sets.

For an isomorphism I would write θ = (θ₀, θ₁), where θ₀: V(G) → V(H) and θ₁: E(G) → E(H). That is, a graph isomorphism is a pair of set functions (that satisfy the appropriate conditions).

A(G) usually means the adjacency matrix of G and Aut(G) denotes the automorphism group. We won't be using the adjacency matrix much.

N(v) is the neighborhood of v and N[v] is the closed neighborhood (see above).
Tutte's λ(G;P,Q) and μ(G;U,V) (Ch. II) correspond to what in the literature is normally denoted by the letter κ. Customarily, λ is used for a different (though related) quantity.
[n] denotes the set {1,2,...,n} for n>1, and [0] denotes the empty set.

Rules for 3-block decomposition

Decomposition based on an edge A

This is what Tutte describes in §IV.3, where he shows how to build Blk₃(G, A).

Decomposition based on cleavages

In §IV.4 Tutte shows how cleavages correspond to virtual edges, but he does not show how to build Blk₃(G) directly using cleavages. I outline the process here.

Start with G.
Find any cleavage. There will be an inseparable bridge, possibly more than one. Pick one such a bridge H, with hinges x, y; then H and its complement K form a 2-separation of G with hinges x, y.
If there is no cleavage in G, go to Step 6. If there is no cleavage in any resulting graph after finding cleavages and splitting into children, go to Step 6.
Split H off from G and introduce a virtual edge A₁ with endpoints x and y; this edge will be added to both H and K.
You now have two graphs: G_1a = H + virtual edge A₁; and G_1b = K + virtual edge that is a second copy of A₁. Call these graphs the "children" of G via A₁.
Repeat the process from Step 2 with G_1a and G_1b, and with their children, and so on until there are no cleavages in any of the resulting graphs. (Don't forget to step the subscript 1 up as you add new virtual edges.)
If a graph has no cleavage, it must be 3-connected or a linkage or circuit, so it is a 3-block.
Now you have the 3-block decomposition of G. Treating the 3-blocks as nodes and the virtual edges as links, you have the 3-block tree Blk₃(G).
Congratulations!

Fundamentals of plane duality for graphs

A plane graph is a graph G embedded in the plane. (It is not a graph. It is a picture of a graph.) The plane graph divides the graph into regions; we call two regions adjacent if they are separated by a common boundary edge. (An isthmus will have the same region on both sides; we treat this as a common boundary of that region with itself.) The planar dual of G is the graph G* obtained as follows:

Put a vertex R* inside each region R.
Draw an edge e* = R*S* between two adjacent regions R and S, one for each separating boundary edge e. e* should cross e to get from one region to the other. (If they are the same region, e* still crosses e.)

Now you have the dual graph G*.

G* can depend on the plane graph, i.e., the drawing of G, not just the abstract graph G. Thus, G doesn't necessarily have a unique dual graph. However, G* is always connected.

For the fundamental properties we'll assume (for simplicity) that G is connected.

First fundamental properties of planar duality:
- Deleting an edge e of G in the drawing gives a dual graph (G\e)* = G*/e. That is, e* is contracted in G*.
- Contracting an edge e of G in the drawing gives a dual graph (G/e)* = g*/e*. That is, e* is deleted in G*.
Second fundamental properties of planar duality:
- A circuit C of G corresponds to a bond C* of G*.
- A bond B of G corresponds to a circuit B* of G*.
The correspondences consist of taking the dual edge e* for each edge e.

To the main course page | my home page.

Math 510 Introduction to Graph Theory Spring 2026