Math 510
Introduction to Graph Theory
Spring 2022

Dictionary

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, by accident.
• Strict graph: No one but Tutte! 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: Also no one but Tutte. Usually this is called an edge-induced subgraph.
• Complement: Tutte's definition is both more general and different from the common one, which I described in class and won't repeat here.
• Special graphs, subgraphs, et al.
  • The neighborhood of a vertex v, written N(v), is the set of vertices adjacent to v. Those vertices are called the neighbors of v. The closed neighborhood, which is the neighborhood together with v itself, is N[v].
  • Thomsen graph: It is an old name for the complete bipartite graph K_3,3 (see below).
  • 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.
  • Matching: A partial 1-factor, i.e., a set of pairwise nonadjacent edges.
      Note on 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". (!)
  • Vertex cover: A set X of vertices such that every edge has at least one endpoint in X.
  • Circuit: Also known as a cycle (but Tutte [correctly] means something different by that), a polygon (rarely, but Tutte has done that), and a circle (mostly 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.
  • Cut: A set that consists of all edges between one vertex set, U, and its complement, V(G)-U, provided there is at least one such edge.
  • Vertex cut: A cut where U = {u}, a single vertex.
  • Bond: A minimal cut.
  • Bridge: Most graph theory people 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.
  • Arc: Most people call this a path (of length n and order n+1). Note that Tutte has not assigned a direction to the arc, only to the labeling. Also, the n+1 vertices are distinct.
    (The word "arc" is often used for a directed edge, but Tutte calls it a "dart".)
• Monovalent vertex: It is widely known as a leaf or a pendant vertex. Tutte's twig (an excellent name when combined with "leaf") is often called a pendant edge.
• 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.
• 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^c for odd m ≥ 5.
• Algebra.
  • Adjacency matrix: It is the V×V matrix, usually denoted by A(G), whose (i,j) entry a_ij equals the number of edges between vertex v_i and vertex v_j.
  • Incidence matrix M(G): It is the V×E matrix defined in § VIII.10 with one +1 and one −1 in the column of each link. It represents the boundary operator ∂: R^E → R^V by ∂(f) = Mf, and the coboundary operator δ: R^V → R^E by δ(g) = M^Tg.
  • Cycle space Z₁: the kernel of the boundary operator ∂. Theorem: It is the span of all circuit chains.
  • Cut space, coboundary space B¹: the span of all cut (or bond) chains. Theorem VIII.42: It is the dual of the cycle space. Tutte explains how this is related to the coboundary operator.
  • Total unimodularity: A matrix is totally unimodular if every nonsingular square submatrix has determinant +1 or −1. In other words, every nonsingular square submatrix is unimodular, which means the determinant is ±1. Totally unimodular matrices are important in optimization; examples are the standard representation matrix of a primitive chain group and the incidence matrix of G. That last explains many of the nice properties as well as the difficult properties of graphs.
  • Primitive chain (correction): The definition should say the non-zero coefficients are "regular" (i.e., units, i.e., invertible).
• 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 of order 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.
  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.

• 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.