Math 381: Graph Theory
Spring 2025
Announcements

Index

• Additional Definitions
• Counting Formulas
• Corrections and Additions
• LaTeX Guidance
• Tests
• Quizzes

Additional Definitions

• I am not always careful to say "multigraph" or "pseudograph" instead of "graph". I hope it will be clear each time, but if not, please ask. In this class we almost always don't use multigraphs or pseudographs, but sometimes we do.

  If we want to emphasize that we don't allow loops and multiple edges, we say simple graph.

• The order of a graph is the number of vertices, |V(G)|.

  The size of a graph is the number of edges, |E(G)|.

• Disconnected means not connected.

• The definition on page 45 of the (connected) components of a graph is not sufficiently clear. If a graph is connected, it has one component. If it is not connected, it has two or more components.

• Let G and H be graphs. An isomorphism between G and H is a function f: V(G) to V(H) such that f is a bijection (one-to-one correspondence) with the property that, for v, w in V(G), vw is an edge in G if and only if f(v)f(w) is an edge in H. (That is what the book means on page 13 when it says the correspondence "preserves adjacency".)

  G and H are isomorphic if there exists an isomorphism. They are not isomorphic if no isomorphism exists.

  One kind of isomorphism is especially interesting. An automorphism of a graph G is an isomorphism of G with itself. Every graph has at least one automorphism, the identity automorphism, which is the identity function from V to V. Some graphs have no other automorphisms. Other graphs have many automorphisms. See the automorphisms handout (pdf).

• We need to distinguish different kinds of connection between vertices. If vertices u and v are connected by an edge, we say they are adjacent. If they are connected by a path, we say they are connected. Two other kinds of connection are: connected by a walk, or by a trail. A path, walk, and trail in a graph are defined on page 50, but the definitions there are a bit confusing, so see the explanation below.

  Connection Theorem. If vertices u and v are connected by a walk (such as, for example, a trail), then they are connected by a path.

• A separating set in G is a set of vertices whose removal leaves a disconnected graph. (Not an empty graph; there must be at least two components after deleting the separating set.)

  A disconnecting set in G is a set of edges whose removal leaves a disconnected graph.

• κ(G), the connectivity of G, is the smallest number of vertices whose removal makes G disconnected or empty.

  In a graph G, take two nonadjacent vertices v and w. Then κ(v,w), the connectivity between v and w, is the smallest number of vertices whose removal leaves v and w in different components.

• λ(G), the edge connectivity of G, is the smallest number of edges whose removal makes G disconnected.

  In a graph G, take any two vertices v and w. Then λ(v,w), the edge connectivity between v and w, is the smallest number of edges whose removal leaves v and w in different components.

• The complement of a graph G (i.e., a simple graph) has the same vertex set as G and its edge set consists of all the edges that are not in G (and none of the edges in G). For example, the complement of K_n has n vertices and no edges.
  The complement of G is supposed to be written as G with a bar over it. On the Web pages it is G^- because I can't type G-bar properly in HTML.

• A clique in G is a set of vertices that are all adjacent. In a complete graph every subset of V is a clique. In any graph, a set containing just one vertex is a clique, and a set of two adjacent vertices is a clique, and in general a clique is the vertex set of a complete subgraph.

• The maximum degree of G is the largest degree of any vertex. The usual notation is Δ(G).

• A graph is called Hamiltonian if it has a Hamilton cycle.

• Two edges are adjacent if they have a common vertex.

• A matching in a graph is a set of nonadjacent edges. If we color the edges of G, the set of edges of any one color is a matching (because adjacent edges can't have the same color). A perfect matching is a matching that covers all the vertices; it is the same as a 1-factor.

• The line graph of G, written L(G), is the graph whose vertex set is V(L(G)) := E(G) and in which e, f (vertices of L(G)) are adjacent if and only if they are adjacent edges in G. The name comes from the fact that "line" is another name for "edge"; the line graph is the graph of edge adjacencies.
  See the line graphs handout (pdf).

Conservative Flows and the Incidence Matrix

• A directed graph (digraph, for short) is a graph where each edge has a specified direction, from one vertex to the other.

• For the incidence matrix M(G) of a digraph G: First number the vertices v₁, ..., v_p and number the edges e₁, ..., e_q. For notation, let edge e_i be directed from t_i (the "tail" of the edge) to h_i (the "head"). Then M(G) is the p×q matrix with column i (for edge e_i) containing +1 in the row of its head, h_i, and −1 in the row of its tail, t_i, and 0's in every other row.
  Theorem IA (Rank of Incidence Matrix). The rank of M(G) equals p − 1, if G is connected.
  Proof idea: The sum of entries in a column = 0 for every column. This implies the rank is not more than p − 1. To prove it is not less, you look at the columns of a spanning tree and show they are linearly independent.

• A flow on a digraph is a function f: E → R (the real numbers). It is conservative if at every vertex v, the flow in = flow out, i.e., (total flow on edges with head v) = (total flow on edges with tail v). Restate this as net inflow at v = 0, where net inflow = flow-in − flow-out. Now, think of a flow as a vector f in R^q, where f_i is the same as f(e_i).
  Flow Matrix Theorem IB. A flow on G (as a vector f in R^q) is conservative if and only if M(G)f = 0 (the zero vector).
  Corollary IC (Theorem 6.2.2). If a flow f satisfies flow-in = flow-out at every vertex other than v, then it is conservative.
  Proof idea: By the proof of Theorem IA, the row of v is the sum of the other rows. It follows that (flow-in − flow-out) at v = −(sum of those numbers at the other vertices).

• The conservative labellings in Section 6.2 are a very special kind of flow. These theorems apply to them, but they are more complicated.

Planarity

• Embedding a graph in a surface (such as the plane or the sphere) means drawing it without self-intersections (the book says "without crossings" but they mean no self-intersections of any kind).

• A plane graph is an embedding of a graph in the plane. It is not a graph! A graph does not have regions. An embedding has regions, and what they are may depend on how the graph is embedded.

• In a plane graph, the degree of a region is the length of its boundary. This is sometimes greater than the number of edges, as an edge sometimes appears twice on the boundary.

• A plane triangulation is a plane graph in which every region is a triangle. Note that this is a property of a drawing of a graph, not of a graph.

• In Exercise 1.1 #7 you have to assume p ≥ 2. What goes wrong if p = 1?


• The definition of a cycle on p. 16 is valid for n ≥ 3 but not for n = 1 or 2.


• In the proof of Theorem 1.3.5, at the top of p. 20, insert the sentence: "Then follow P₂ back to v₁." before "Then we have a cycle."


• The graph I in Figure 1.2.5 is the one without a label. (It's the icosahedral graph.)


• The graph of Figure 2.1.5 is not critical. That of Figure 2.1.6 is critical. (You should prove these statements!)


• In Exercise 2.1 #4, you should find
    (a) any critical subgraph;
    (b) a critical subgraph whose chromatic number equals that of the whole graph.
  (The same goes for #5.)


• In Exercise 2.1 #15(a), the subgraph that is forbidden is K₃, not K₄.


• For Exercise 2.1 #20 you should know the definition of a component of a graph. See page 45.


• Vizing's Theorem 2.2.2 is actually true of all graphs, not just regular graphs.


• Theorem 2.2.4 is valid only for n ≥ 2.


• The last line on p. 38 (the one for (C_n)) should read
        n-1, n-2, n, n-3, n+1, n-4, ..., 2n-2, 2n-1, x.
  (This is equivalent to the printed line, but the printed line doesn't follow the pattern it's supposed to.)


• On page 45, the definition of a component is incomplete. See the definition above.


• Problem 2.4.12 has a space with four underlines for the answer. This does not mean four words. It doesn't mean anything except a blank space.


• Section 3.1: The definitions of path, closed path, and cycle are rather muddled. A path is a trail in which no vertex is repeated. A closed path is a closed trail (a circuit) in which no vertex is repeated except for the terminal vertex. Therefore a "closed path" is not a path! Sorry, that's the way it is.
      A trail is open if it is not closed. An Eulerian trail in a pseudograph is a trail that contains every edge of the pseudograph. An Eulerian circuit in a pseudograph is a circuit that contains every edge of the pseudograph. Vertices need not be included in an Eulerian trail or circuit, despite what the book says on page 55.
      An Eulerian graph is a graph that has an Eulerian trail.


• Theorem 3.1.1 (corrected). If a pseudograph G has an Eulerian circuit, then G is connected (except for isolated vertices) and the degree of every vertex is even.


• Theorem 3.1.6 (corrected). Let G be a pseudograph.
  (a) G has an Eulerian trail if and only if it is connected (except for isolated vertices) and has at most two vertices of odd degree.
  (b) G has an open Eulerian trail if and only if it is connected (except for isolated vertices) and has precisely two vertices of odd degree.

• You can download a LaTeX compiler from the TeX Users Group Website. There is a very, very easy startup guide. All the downloads here are free. I recommend the TexLive download.

  I use TexShop in the TexLive download. I find it very easy to use for preparing Tex documents from start to finish. It also has a good search engine (which supports regular expressions, if you know what that means).

• I am linking a sample Latex source file that you can use, and the compiled PDF obtained from it. It shows how to type paragraphs and equations and how to include graphics.
  Additional tips:
  • In Latex you can include a figure with the following command:
    \includegraphics[scale=1.5]{filename}
    The scale factor can be any positive number. If a graphic is too big, you can make it smaller. If a graphic is too small, you can make it bigger.
  • A blank line between your answers to different questions makes it easier for me to read. You can make a blank line in Latex with \bigskip which should be preceded or followed by a blank line.

• There is an online Latex compiler called Overleaf that has been recommended by some people.

Tests and Quizzes

	A	B	C	D	F

	A	B	C	D	F

	A	B	C	D	F

Quizzes