Math 381: Graph Theory
Spring 2013
Announcements

Tests

	(1) 1	(2) 10	(3) 10	(4) 12	(5) 8	(6) 10	(7) 5	
	(8) 5	(9) 7	(10) 8	(11) 10		(12) 5 + 9 + (bonus) max 10

	A	B	C	D	F
	80-100	65-79	47-64	40-46	0-39

	A	B	C	D	F
	84-100	62-83	42-61	36-41	0-35

	A	B	C	D	F
	110-140	85-109	58-84	50-57	0-49

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

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

  • 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. (Remark: 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).

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

  • 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 (that means they have a common vertex 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).

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


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


• Here is a series of slides from a lecture on magic graphs (called "supermagic").



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.


• 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 Sect. 10.3 they often say "circuit of a rotation". What they mean is a region of an embedding of the graph in a surface. "Rotations" are a technical tool that I will avoid.


• 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 T_γ (by me) and S_γ (in the book). T₀ = S₀ is the sphere, T₁ = S₁ is the torus, T₂ = S₂ is the double torus, etc.
  • The Euler formula for graphs embedded in these surfaces is:
    Theorem Tg (Euler's polyhedral formula 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).
  
  
  • Here are pages with diagrams for T₁ (the torus) and T₂ (the double torus), or both T₁ and T₂, that you can use for drawing graphs.
  
  
  • You can apply Theorem Tg 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 T_γ. 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.