Math 381: Graph Theory
Spring 2021
Announcements

Index

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

Tests and Quizzes

	A	B	C	D	F
      110-145+	80-110	50-80	45-50	0-45

The midterm solutions are available.

Final Exam (Take-home, 5/19-26)

The final exam is comprehensive. Expect greater proportional emphasis on topics after the midterm than on the earlier material. (That does not mean any specific proportion.)

The (approximate) guidelines for the grades are:

	A	B	C	D	F
	160-190 125-160 85-125 76-85   0-75				

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


• We have some additional theorems or possible theorems for Section 1.3.
  1. Theorem 1.3.A. The average degree of a tree is < 2. (Proved in class.)
  2. Alleged Theorem 1.3.B. A graph is a tree if and only if it is connected and its average degree is < 2.
  3. Theorem 1.3.C. A graph is a cycle if and only if it is connected and 2-regular.
  4. Theorem 1.3.D. Given a tree T and an edge e not in T but whose vertices are in T, there is a unique cycle in T ∪ e.


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


• Exercise 3.1.1. Find an Eulerian circuit—it need not be unique!


• Exercise 3.1.13. You need to assume that G is connected.


• Exercise 3.3.17: The graph you find should also be connected, in addition to the other properties that are specified.


• The order of a g-cage cannot be known in general but we can prove a lower bound. Here is the theorem for reference.
  Theorem 4.2.A. A g-cage has at least b(g) vertices where
            b(g) = 3 · 2^(g-1)/2 − 2, if g is odd,
            b(g) = 2 · 2^g/2 − 2, if g is even.



Chapters on planarity and surfaces

• Be sure to see the relevant definitions in the definitions list above.


• The 6-Color Theorem: Every planar graph can be colored in 6 colors.


• The 4-Color Theorem for Triangle-Free Graphs: Every planar graph without a K₃ subgraph can be colored in 4 colors.


• Definition for Exercise 8.3.7: 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.


• Theorem 8.1.A. Let G be a graph. If G is maximal planar, every plane drawing of it is a plane triangulation. Conversely, if G has a plane drawing that is a plane triangulation, then G is maximal planar.
  
      I showed how to prove this in class. The first part uses the definition of a maximal planar graph. The converse uses Theorems 8.1.2 and 8.1.3.


• Theorem G. If G is a planar graph and has girth g (where 3 ≤ g < infinity), then q ≤ [g/(g-2)](p-2).
  This is a generalization of Theorems 8.1.3 and 8.1.5.


• (Supplement to Chapter 9.) Here are some useful general theorems based on Theorem G.
  • Theorem CR. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then
                cr(G) ≥ q - [g/(g-2)](p-2).
  • Theorem SPL. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then
                σ(G) ≥ [(g-2]/g] q - (p-2).


• Exercise 8.4.9 should read: Find the smallest graph that is planar and regular of degree 3 and has a plane drawing where every edge has the same geometric length.


• The proof of Theorem 8.4.1 is not stated exactly right in the book. In the middle, what is stretchable is not G - h but the plane drawing of it that we already have. So what we have to prove is not that all planar graphs are stretchable, but that all plane drawings are stretchable.


• The definition of stretchability after Theorem 8.4.1 is for graphs. There is a similar definition for a plane drawing of a graph. A plane drawing is called stretchable if the edges in the drawing can be straightened (the vertices can be shifted around if necessary) without introducing any forbidden intersections in the straightening process.


• Sect. 9.1: Kuratowski's Theorem means the combination of Theorems 9.1.1 and 9.1.2.


• Sect. 9.1, p. 180: A simple drawing must also satisfy
        d) no edge passes through any vertex.


• The proof of Theorem 9.1.4 should consider the possibility that the two quadruples intersect in more than two vertices. (It is not hard to fix the proof.)


• Theorems 9.2.1 and 9.2.2 require the assumption that p ≥ 3.


• The lower bound
              (1)       θ(K_n) ≥ floor[(n+7)/6]
  stated on p. 192 can also be, and should be, stated as
              (2)       θ(K_n) ≥ ceiling[(n+2)/6].
  Proposition. (1) and (2) are equal. (That's just algebra but it is not obvious.)


• In Figure 9.2.4 there are three duplicate edges. (Can you find them? This doesn't invalidate the proof that σ(K₉) ≤ 6.)


• Note that Exercise 9.3.2 uses only the easy half of Theorem 9.2.4.


• On page 208, the definition of a rotation of a graph doesn't need the degrees to be 3. They can be anything, as the book says later on.


• On page 209, "each direction in at least one" should be "each direction in exactly one".



Supplement to Section 10.3

• Embedding a graph in a surface means drawing it on the surface without crossings or any other self-intersection.


• In Theorem 10.3.7 the ceiling function should be the floor function.


• In Theorem 10.3.8, "and γ(G) ≤ g" should be "with γ(G) ≤ g".


• The sphere with γ handles is written S_γ. S₀ is the sphere, S₁ is the torus, S₂ is the double torus, etc.
  • The Euler formula for graphs embedded in these surfaces is:
    Theorem Sg (Euler's polyhedral formula for the sphere with handles). For the sphere with γ handles,
                      p - q + r = 2 - 2γ,
    assuming that p ≥ 3 and all the regions can be flattened (which means they have no part that's cylindrical).
  
  
  • You can apply Theorem Sg to get an idea of whether a given graph G can be embedded in a given surface. Specifically, look for a lower bound on the number of handles, similar (in a very general sense) to the lower bounds for thickness, crossing number, and splitting number. The actual smallest number of handles needed to embed G is the genus of the graph G, written γ(G).
  • Use that lower bound to get an idea of which complete graphs K_n or complete bipartite graphs K_m,n can be embedded in a given surface S_γ. Specifically, look for a lower bound on the number of handles, and then find an embedding using only that many handles, if you can! (The lower bound theorems are stated in Sect. 10.3, but their proofs are very technical.) Try the torus, and if you're ambitious, try the double torus. The results get cute.
  • Here are pages with diagrams for S₁ (the torus) and S₂ (the double torus) that you can use for drawing graphs.

• 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. (It is in HW O.)
  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. Some of your included graphics are tiny; you can make them larger with the scale factor. If a graphic is too big, you can make it smaller.
  • 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. Don't do it with \\; that is poor coding.

• There is an online Latex compiler called Overleaf that has been recommended by some people. (I use a downloaded compiler because I use LaTeX all the time.)