Supplementary Notes for Graduate Graph Theory

A partition of a set X is a class of nonvoid subsets of X that have pairwise disjoint intersection and whose union is X.

G denotes a graph. V(G) denotes the vertex set and E(G) the edge set of a graph G. Often I simplify these to V, E, if G is known to be the graph we're talking about. It's common (I mean `frequent', not `vulgar') to write G = (V,E) to mean a graph G with V(G) = V and E(G) = E (the same as Aigner's notation G(V,E), which is unusual). It's also common to write, without further explanation, V' and E' for V(G') and E(G'), V₁ and E₁ for V(G₁) and E(G₁), etc.

The letters v and e always denote vertices and edges, respectively, unless otherwise stated. To indicate that e has endpoints u and v (also said: e is incident with the vertices u and v) I write e:uv. (In a simple graph one can regard e as = uv (the unordered pair), but in a multigraph uv may not denote a unique edge so one shouldn't say e = uv.)

The order of a graph is |V|, the number of vertices. Some people say ``size'' for |E|, the number of edges, but this is not generally accepted. In our class let's say ``size'' for any indicator, not necessarily always the same, of how big a graph is. This might be the order |V|, or |E|, or |V| + |E|, or something else.

If we have a definite graph and X is a subset of V, then X^c is another way of writing V\X, the complement of X in V.

A graph G induces a partition of its vertex set, pi(G), whose parts are the vertex sets of the connected components of G. We might call this the connected partition of G, although there's no standard name.

An isthmus or bridge is an edge whose deletion leaves a graph with more connected components.

The complement of a simple graph G is the graph G^c (more commonly, G with a bar over it, but HTML doesn't allow me to write that) with the same vertex set V(G) but the complementary edge set: that is, E(G^c) = E(K_n)\E(G). A nonsimple graph doesn't have a well defined complement.

Here are some concepts about two edges, e and f, in a graph: They are called parallel if they have the same endpoints; this is the same as what we call ``multiple edges''. They are in series, or a series pair, if every polygon that contains e or f contains both e and f. They are adjacent if they have a common endpoint.

A clique in G is a set of pairwise adjacent vertices. In some sources, it's a maximal such set , or a maximum-sized one. I don't use those definitions; instead I speak of a maximal clique, which is a clique not properly contained in any other clique, and a maximum clique, which is a clique having the maximum possible number of elements. A set of vertices in G is independent or stable if its members are pairwise nonadjacent.

The hypercube graph, in full the n-dimensional hypercube graph, Q_n, is defined in the book. Of course it is the graph of vertices and edges of an n-dimensional geometrical hypercube. (Strictly speaking, the name cube graph should be applied only to Q₃. Since I saw the term ``tesseract'' for a 4-dimensional hypercube -- see the very funny story by R.A. Heinlein, ``--And He Built a Crooked House'', in Fantasia Mathematica -- we could call Q₄ the tesseract graph, although I've never seen that done.

The hyperoctahedral graph, or in full the n-dimensional hyperoctahedral graph, K_2(n), is K_2n with a 1-factor deleted. It is the graph of an n-dimensional geometrical hyperoctahedron. The 3-dimensional one is the octahedral graph.

Similarly there are the dodecahedral graph and the icosahedral graph.

All of these geometrically based graphs are also known (in graph theory) under the names without the word graph, e.g., the hypercube or hyperoctahedron.

A 2-connected graph is sometimes called a block graph (or just a block). A maximal 2-connected subgraph of G is called a block of G (or just a block if we know we're talking about subgraphs of G). Note that a block of G is an induced subgraph. Thus, it may contain loops.

For some purposes we need to exclude loops from a block (or, to treat a loop as if it were a block in itself). An edge block of G is either a maximal loopless 2-connected subgraph, or a loop together with its incident vertex.

If there is doubt about which kind of block we mean, we can call an ordinary block a vertex block.

We say H is a subgraph of G if V(H) is a subset of V(G), E(H) is a subset of E(G), and the vertex-edge incidence relation in H is that of G restricted to E(H). A subgraph spans G if its vertex set is V(G). We say H is a topological subgraph of G if G has a subgraph that is isomorphic to a subdivision of H.

An induced subgraph of G, induced by a subset X of V, has vertex set X and edge set consisting of all edges whose endpoints are contained in X. Notation: G:X or G[X]. (The empty set is allowed; it induces the empty graph.) If one deletes a set Y of vertices, this gives G:(V\Y), also written G\Y.

Deleting an edge set S from G yields the spanning subgraph G\S = (V, E\S). The deletion of E\R is also called the restriction of G to R and written G|R or (V, R). Contracting S yields the graph G/S whose vertex set is pi(V,S) (also written pi(S) if G is understood) and whose edge set is E\S. An edge e:xy of E\S has for its endpoints in G/S the parts X and Y (members of pi(S)) such that x belongs to X and y belongs to Y. A minor or subcontraction of G is any graph resulting from any sequence of contractions and taking subgraphs. (It is always sufficient to take a subgraph and then do one contraction, or to contract once and then take a subgraph.)

Splitting a vertex v in G means replacing v by two vertices and a connecting edge, with each incidence (in G) of an edge with v becoming an incidence of e to one of the two new vertices. (Splitting a vertex is the opposite of contracting an edge.) Sometimes people mean by splitting that each new vertex is incident with at least 2 original edges; we might call this nontrivial splitting.

Subdividing an edge e means replacing any edges of G by a path of length 2 or more. (Or sometimes exactly 2; this might be called subdividing e once; it is a trivial kind of splitting.) A subdivision of G is a graph obtained by subdividing any edges of G (including not subdividing any edges).

A walk in G is a sequence of vertices and edges, (v₀, e₁, v₁, e₁, ..., e_k, v_k), with k >= 0, such that the endpoints of edge e_i are v_i-1 and v_i for all i = 1, 2, ..., k. The length of the walk is k, the number of edges. The walk is closed if v₀ = v_k and its length is positive (it seems to make sense that a `closed walk' must automatically have at least one edge).

Note that a walk is not a sequence of vertices nor a sequence of edges. However, the edges (or sometimes the vertices) can be omitted when there is no danger of ambiguity. (This is one place the book made a mistake.)

A trail is a walk in which no edge is repeated.

A path is a trail in which no vertex is repeated. (Therefore the two end vertices are different unless k = 0.)

A closed path, or circuit, is a closed trail in which no vertex is repeated except that the initial and final vertices are the same. Note that a closed path is not a path! The girth of G, g(G), is the length of a shortest circuit in G.

Paths P and P' in a graph are called internally disjoint if they have in common no edges and, if any vertices, only ones that are endpoints of both. A set of paths is (pairwise) internally disjoint if each pair are internally disjoint. (This is normally applied to paths that have the same endpoints.) (Aigner calls this ``disjoint'' but that is not strictly correct.)

The term `path' may mean either a walk that is a path, or a graph underlying such a walk. Be sure it is clear whether a `path' is intended to be a walk or a graph. Usually it will be clear enough.

The same holds for `circuit'.

A drawing of a graph on a surface is allowed to have crossing edges, but no edge intersects itself and no edge goes through a vertex except at its end. An embedding is a drawing in which no two edges intersect except at a common endpoint. An edge is drawn as a curve in the surface. We will always assume that the edges are topologically nice curves--this means, at the least, that each open edge (that is, excluding the endpoints) has a regular neighborhood, i.e., a neighborhood that is homeomorphic to an open disk and that doesn't meet any other part of the graph. The genus of G, gamma(G), is the smallest g such that G embeds in T_g (i.e., S_g). The crosscap number or nonorientable genus (the latter is a misnomer, as I've explained in class), gamma-twiddle(G), is the smallest h such that G embeds in U_h (i.e., N_h). The demigenus d(G), or Euler genus (also a misnomer), is min{ 2gamma(G), gamma-twiddle(G)}.

An embedding (but not any drawing) divides the surface into regions or countries or (2-dimensional) faces, which are the topological connected components of the complement of the embedded graph. (The closure of a region may be called a closed region.) Each edge has two sides: these are the two components of a regular neighborhood of the edge. An embedding is cellular (also called a 2-cell embedding) if every region is homeomorphic to an open disk.

A boundary edge of a region is an edge that is contained in the closure of the region. The boundary of a region could be either of three things:

1. The closed region - the (open) region. This is too topological to be interesting to us most of the time.
2. The subgraph consisting of the vertices and edges in the closure. This is the boundary (sub)graph of the region.
3. A closed walk that goes completely around the region, including all the vertices and edges in the closed region. This is a boundary walk of the region. A boundary walk is understood to traverse each boundary edge one time for each side of the edge that is in the region; thus if an edge bounds the same region on both sides, it will be traversed twice in the walk.

The surface dual of an embedded graph G is the graph whose vertex set is the set of regions of G, with an edge connecting two dual vertices for every edge of G that separates the corresponding regions. This includes edges with the same region on both sides, which in the dual become loops. A dual G* of a graph G is a surface dual of an embedding of G in the plane (or sphere). We don't call a dual constructed in any other surface a dual graph of G. (Why, will become known at a suitable time.)

A rotation system (sometimes rotation scheme), R, for a graph consists of a rotation R(v) for each vertex. R(v) is a cyclic permutation of the edge ends incident with the vertex. I say ``ends'' because a loop has two ends at the same vertex; if we don't have loops, we just permute the edges incident with v. When G is simple, it suffices to list the other endpoint of each edge; thus we specify R(v) by a cyclic permutation of the neighbors of v. This last is the usual practice since we rarely, if ever, need to worry about nonsimple graphs. If G is cellularly embedded in an orientable surface S and we specify a `counterclockwise' direction at every vertex in a consistent way around the whole surface (this is possible precisely because S is orientable), then we can read off a rotation at each vertex v by reading the cyclic order of edges around v in the counterclockwise direction. This gives a rotation system from a cellular embedding. (Aigner calls the whole system a ``rotation'', but I feel that's a little confusing; anyway many people use the names I've given here.)

The chromatic number of G is denoted by chi(G). `The chromatic polynomial of G is denoted by chi(k) or p(k) or chi(G; k) or p(G; k).

The chromatic index of G is also called the edge chromatic number; it is denoted by chi'(G). (As we discussed in class: in edge coloring it isn't necessary to have loops, because either a loop makes the graph not edge colorable, or it behaves like a bridge to an extra vertex.)

According to Vizing's Theorem, every simple graph has chromatic index equal to Delta(G) or Delta(G) + 1. Graphs of the first type are said to be in Class 1 (Class Gamma₀ in our book); those of the second type are said to be in Class 2 (Class Gamma₁ in our book). (I don't know where the Gamma notation comes from. I've never seen it before.)

The colorings we've been looking at are sometimes called proper colorings and the term ``coloring'' is generalized to an arbitrary function f: V --> color set. Then f might have improper edges, which are defined as those edges e:uv such that f(u) = f(v). (Every loop, for instance.) I write I(f) to denote the set of improper edges of a coloring f.

Expressions for the chromatic and related polynomials

• Activities. We are given a spanning tree T in a connected graph (G, with p vertices and q edges), and a linear ordering of the edges (which I'll indicate by subscripts, writing the edges as e₁, ..., e_q). An edge is called internal if it is in T, and otherwise external. Each internal edge e belongs to a unique polygon C_e contained in T union {e}, and each external edge e belongs to a unique bond B_e contained in T^c union {e}. We call e internally (or externally) active if it is the largest edge in C_e (or B_e, respectively). (Some people prefer to say ``smallest'', but it's equivalent by reversing the edge ordering.) Let t<sub>ij</sub> be the number of spanning trees in which exactly i edges are internally active and j are externally active. If we write the ``positivized'' chromatic polynomial psi_G(k) in the form
  psi_G(lambda) = lambda^c Sum_i t_i(lambda+1)ⁱ
  (where c is the number of connected components of G), then t_i = t_i0 (special case of a theorem of Tutte's).

  The generating function of all colorings, proper or improper, is called the dichromatic polynomial, Q_G(u,v). It can be defined conveniently, but indirectly, by defining

  Q-bar_G(lambda,v) = Sum_f v^#I(f) = Sum_m I_mv^m,
  where I_m = the number of colorings in lambda colors that have exactly m improper edges. Then

  Q_G(u,v) = v^-p Q-bar_G(lambda,v).
  Tutte proved his chromatic-polynomial formula just mentioned more generally for the dichromatic polynomial, but I'll omit the details.

A weighted graph has edges labelled with real numbers, say w(e). The weight of an edge set or subgraph, w(S), is the sum of the weights of the edges in G. Sometimes the weights are elements of a different additive system, e.g., Z, or Z_m for some positive integer m; we might call this a Z-weighted or integer-weighted graph, or a Z_m-weighted graph, respectively.

A signed graph has edges labelled by signs, + or -, i.e., each edge is called positive or negative. The sign of an edge set or subgraph is the product of the signs of its edges.

Some of these comments are included in the preceding definitions.