Graph Theory (Math 224)

I am in Reiss 258. See my index page for office hours and contact information. For background info see course mechanics . New: schedule for midterms et al.

The text is "Introduction to Graph Theory" by Richard J. Trudeau, which is in paperback from Dover Publications, NY, 1994; still in print and available in the bookstore or from amazon.com - here is a picture .

I've got a page with some basic material on graph theory here . You can also find definitions (not always the same!) for various graph-theoretic terms, and even tutorials, on the web.

Back to the classroom page .

Dec. 11, 2005

As I told you by e-mail, there are practice problems on top of the file cabinet just to the left of my office door in Reiss 258. When you've tried these, you may want to look over the answers to the practice problems.

For the graph theory final (Reiss 281, Monday Dec. 12 at 9 = 11 am) be prepared to demonstrate your knowledge of graph theory. I won't expect anything too tricky in the nature of a proof. You should be familiar with the basic concepts without worrying about regurgitating definitions. I realize that one can get confused trying to recall the distinction between, say, book thickness and genus - but if you are briefly reminded what it means and then given a concrete example, I would expect that you can then work out, say, the Euler lower bound.

If you are seeing concepts and theorems for the first time, it is quite difficult to use them correctly. On the other hand, if you have reviewed these topics before, then they should be easy to apply in concrete cases.

The exam will cover everything that we've handled in class, whether from the book or not. You should make a point of knowing a bit more about your own topic (that of your group) from the presentation but also something from at least one of the other topics.

Our assignment for this week will be based on the groups we determined in an earlier class:

Group membership lists:
1. Group 1: Barbero, Carter, Hipp, Limarzi, Piro
2. Group 2: Bouton, Browning, Griauzde, Mitzner, Wallace
3. Group 3: Grant, Liang, Punzalan, Sheedy, Lixandru
4. Group 4: Alston, Bergeron, Detjen, King, Lebec, Marino

Here are the topics we will study by group this week. Each group will have a half-class period next week in which to present their topics to the rest of the class. The final exam will include one question on the topic your group presents and a more superficial question on one of the topics given by the other groups.

1. Orthogonality and cliques. (1) The clique number of a graph and graph family; (2) Orthogonality graphs; (3) The square of the orthogonality graph is complete; (4) Clique number of nearly orthogonal graphs; (5) Clique number of a random graph
2. Blocks and book thickness. (1) The block-cutpoint tree decomposition of a graph; (2) The genus of a graph is the sum of the genuses of its blocks; (3) The book thickness of a graph is the maximum of the book thicknesses of its blocks; (4) Complexity of invariants; (5) The square of a block is Hamiltonian
3. Book thickness of planar bipartite graphs. (1) Whitney's Theorem: Every triangulation of the sphere without any separating triangles has a Hamiltonian cycle; (2) Tutte's Theorem: Same conclusion for 4-connected planar graphs; (3) Overbay's Theorem: Same conclusion for planar graphs in which no triangle is separating; (4) Applications
4. Modern approaches to the 4 color theorem. (1) Whitney's Theorem; (2) Variants of the 4CT in terms of edge-coloring; (3) Trees as devices to multiply or split apart a signal; (4) The 4CT as a statement about vector cross-product

Just added: Practice problem and midterm background. The practice problems are now available for your study. To supplement the class definitions, I've written up a midterm background page.

Be sure you can handle the basic lower-bound calculations which we've done a number of times now. These give lower bounds for genus and Hamiltonian book thickness for graphs based on Euler's formula and its consequences. You should know the basic definitions and how to use them.

I think you need more time for review so the midterm is postponed until Monday Nov. 21. It will cover everything since the last midterm (as well as basic graph-theoretic concepts which were previously introduced), including the material covered in class which is not in the text. As I said in class, Nov. 23 is optional. For the week of Nov. 28 through Dec. 2, you will be working in four teams (as we did in class a week or two ago), with those who weren't here that day being on a new team. Each of the teams will have 20 minutes on Dec. 5 and 7 to make a presentation to the entire class (allowing a few minutes for questions).

The final exam at 9:00 am on Dec. 12 will set up some scenarios on which you will be asked to comment. So the emphasis for the final will be on using graph theory as a tool to formulate problems, asking only for you to be familiar with a reasonable proportion of the material we've covered in class, including at least one of the class presentations in addition to that of your own group.

The written homework assignment for Monday remains: find the Hamiltonian book thickness of Q_d. This involves (1) finding a lower bound on bt_{ham}(Q_d), which is the least number of pages needed for Q_d minimized over all cyclic orders omega on the vertices which induce a Hamiltonian cycle (emulate what I did in class for K_p,p (the complete bipartite graph with p red and p blue vertices), and (2) constructing actual book embeddings for Q_d (recursively as with genus). This will generalize the two embeddings given in class of Q_2 in 1-page and Q_3 in 2-pages. See the midterm-background page above for more on this definition.

In class on Wed., we went over the proof that if there exists a cyclic order omega on the vertices of G such that X(G,omega) is bipartite, then G is planar. Then we discussed the general problem of determining the chromatic number of X(G,omega). In fact, we use the term book thickness (of G,omega), denoted bt(G,omega), for chi(X(G,omega)). This is just the least number k of colors such that, if the vertices are placed around a circle in order omega, one can color each edge of G with one of the k colors so that no two edges with the same color cross at an interior point. The set of all edges with the same color can be viewed as determining a "page" and each page can use up at most n-3 interior edges (where n is the number of vertices of G). Hence, the least number of pages is at least m_i/(n-3), where m_i is the number of interior edges of (G,omega), i.e., which join nonconsecutive (w.r.t. omega) vertices of G. For K_n, m is n(n-1)/2 and for any omega there are n edges joining consecutive vertices so m_i is n(n-3)/2 and hence K_n needs at least n/2 pages (and since the number of pages is an integer, bt(K_n) is at least {n/2}, where {a} means the least integer greater than or equal to a and bt(G) is defined as the minimum of bt(G,omega) over all possible omega.

The above is a quick sketch. Check with your classmates for the full version.

For Friday, Nov. 11, "show me" exercise, construct drawings of K_n (odd and even case are different) to show that the lower bound of {n/2} pages is achievable. For Monday, I'm going to ask for the analogous problem for the graphs Q_d.

As promised, here is something to work on for the next few days. The problem on the page below on crossing graphs is due on Wed., Nov. 9. There will be an additional set due on the 14th, and the midterm on the 16th will cover the material from the text as well as the additional topics that we've looked at in class. Note that the crossing-graph web page is somewhat modified from the original form so be sure to look again - also the assignment is now different and shorter, just one problem.

For Friday, 10/28, there was a homework assigment to derive a lower bound on genus using the general upper bound on m from Euler's formula and then to apply this to obtain a lower bound on the genus of the graph Q_d.

Recall that an embedding of graph G in surface S is called a 2-cell embedding if S - G is a disjoint union of subsets (the regions of the embedding) and each of these subsets is homeomorphic to an open disk. (A and B are homeomorphic means that there exists a continuous mapping from A to B and a continuous mapping from B to A so that both compositions are the respective identities.)

Every graph G has embeddings in surfaces S_k when k is large enough (e.g., k = number of edges) and so there is a _least_ such nonnegative integer k which is defined to be the _genus of G_ denoted gamma(G) (the book uses g for genus but we use g for girth). The theorem which we use repeatedly is that if G is embedded in S_k for k=gamma(G), then the embedding _must_ be a 2-cell embedding. For any 2-cell embedding of G in S_k, Euler's formula holds:

n - m + r = 2 - 2k,

where n,m,r denote numbers of vertices, edges, and regions. The general upper bound on m (the number of edges) in a graph G with n vertices and girth g (girth = length of shortest cycle) provided that G has a 2-cell embedding in S_k is

m <= (g/(g-2))(n - 2 + 2k)

which generalizes the bounds m at most 3n-6 (or m at most 2n-4) for planar graphs with girth at least 3 or at least 4, resp. If you haven't done this hw problem yet, do it for Monday 10/31. Otherwise, there is no written homework for Monday, but do read Chapter 7 on genus. I suggest you skip the section on g-platonic graphs. Look, instead, at Heawood's formula but try to find your own argument; the one in the book is too complicated!

For Wed. 10/26, use the formula m <= 2(n - 2(1-k)) which holds for any bipartite graph G with n vertices and m edges which has a genus embedding in the surface S_k with k handles, to find a lower bound on k when G is is the cube Q_d. We showed in class that Q_d has n = 2^d vertices and m = d*2^(d-1) edges (where "*" means "times" and "^" indicates superscript). And we noted in class that Q_d is bipartite (for d at least 1).

THis is not a written assignment but I'll allow some of you to put your solutions on the board.

For Mon. 10/24, homework due for collection: Find an embedding of K_6 in the projective plane; i.e., draw K_6 in the interior of a disk but allow edges to go through the boundary where opposite points on the boundary ("antipodal" points) are identified together. Also, mimic the construction (done in class) of Q_4 on the torus obtained by taking two copies of Q_3 in the sphere and attaching two handles connecting two opposite faces in one copy of Q_3 to the respective opposite faces in the other copy of Q_3. Your goal is to figure out (and sketch the argument for) the genus of Q_5 - that is, you will construct an embedding of Q_5 on a surface by attaching a certain number of handles between two copies of Q_4 in the torus.

For Monday 10/17, read (as much as needed of) Chapter 8 (we'll come back to chapter 7 later) and write up problems #2 and 3 on p. 188.

We defined the "cube graph" Q_d = (V,E) in class as follows:

V = {0,1}^d  (that is, the vertices are all length-d binary strings,
where binary means 0 or 1

If alpha and beta are two binary strings in V, then [alpha,beta] is
an edge in E if and only if alpha and beta agree in every coordinate
except for one where they are different.  

Q_0 is K_1; Q_1 is K_2; 

Q_2 is C_4 (see below)


    (0,0) *------------------* (1,0)
          |                  |
          |                  |
          |                  |
          |                  |
          |                  |
          |                  |
          |                  |
          |                  |
    (0,1) *------------------* (1,1) 

Q_3 is the graph determined by the corners and
edges of the 3-dimensional cube, and so forth.

For Wed. 10/19 find as many basic properties of these cube graphs as you can and write up your answers so that I can walk around and see at a glance that you've done something.

Here is some information for the take-home problem which is due tomorrow (Friday 10/14). If you haven't done this problem (that refers to a couple of you) please do it immediately and make sure I have your write-up by Wed. class.

Here's a second try to explain some of the terminology.

The distance between two vertices is the minimum length of 
all paths which connect them, where the length of a path is
the number of edges in the path.

Let G be a connected graph. The eccentricity of a vertex v
is the greatest distance from v to any other vertex of G.
So distance is a minimum over path-lengths, while eccentricity
is a maximum of distances.

The radius of a graph is the minimum eccentricity of the
vertices, while the diameter of a graph is the maximum
eccentricity of the vertices.  Since the minimum of any
set of real numbers is at most the maximum of the set,
it is immediate (nothing to prove) that rad(G) <= diam(G).

Prove the theorem: diam(G) <= 2*rad(G); i.e., diameter is
at most twice the radius.  The lemma I mentioned earlier
(which is called the "triangle inequality" for distance
in graphs) is needed in the proof.  

The triangle inequality says that for all vertices u,v,w,
the distance from u to w is at most the sum of the 
distance from u to v plus the distance from v to w.

First prove the lemma and then use it to do the problem.

For further practice you should try as many of the following as you can.

Still more review problems.

(1) If G is a connected graph and if H_1 and H_2 are 
longest paths in G, then H_1 and H_2 must have at least
one vertex in common.

(2) If G is not connected, then G-bar (the complement)
_is_ connected.

(3) Construct a cubic graph (i.e., regular of degree 3)
which has 2n vertices but no triangles.

Recall that a cutpoint is a vertex whose removal makes
the number of connected components increase.

(4) What is the largest number of cutpoints in a graph
with p vertices?

(5) If v is a cutpoint of G, then v is not a cutpoint
of G-bar.

(6) A vertex v of G is a cutpoint if and only if there
are points u and w adjacent to v such that v is on every
u-w-path.

(7) A graph is nonseparable if it is connected, nontrivial,
and has no cutpoints.  A block of a graph is a maximal
nonseparable subgraph.  If G is nonseparable, we call G
a block.  The square G^2 of a graph G is obtained by 
adding a new edge vw whenever v and w are not adjacent
but some vertex u is adjacent (in G) to both v and w.
(E.g., the square of C_5 is K_5.)  Now show that: 

The square of every nontrivial connected graph is a block. 

(8) A bipartite graph G is a graph whose vertex set V(G)
has a partition V(G) = V_1 U V_2, where V_1 and V_2 are
disjoint (that's what "partition" means), and where each
edge in G joins a vertex in V_1 to a vertex in V_2.
A bipartite graph is complete if each pair of vertices
v_1 in V_1 and v_2 in V_2 are joined by an edge.

Characterize the trees which are complete bipartite.

(9) A graph is bipartite if and only if every cycle has
even length.

Recall that a bridge is an edge whose removal increases
the number of connected compoonents.

(10) An edge e of G is a bridge if and only if e does
not belong to any cycle of G.

(11) Let G be a connected graph with at least 3 points.
The following statements are equivalent:
(a) G is a block.
(b) Every two vertices lie on a common cycle.
(c) Every two edges lie on a common cycle.

Recall that G is n-connected if the least number of 
vertices whose removal makes G disconnected or trivial
is at least n; that is, kappa(G) >= n.  (The text uses
c instead of kappa.)

(12) Every n-connected graph with p vertices has at 
least pn/2 edges.

(13) Every 5-connected planar graph has at least 12
vertices. Construct one such graph.

Recall that Euler's formula implies that m is at most
3(n-2) for connected planar graphs with at least 3
vertices, where n and m denote the number of vertices
and edges, resp. Further, if the graph has no cycle
of length shorter than g, then the upper bound on m
can be improved to h(n-2), where h = r/(r-2).

(14) Use the improved version above to show that the
Petersen graph is not planar.

(15) Suppose you know that for connected graphs drawn 
on the torus which have no triangles m is at most 2n.
What can you say about the chromatic number of such a
graph?

Homework due Mon. 10/3.

 p. 140 #6 and #8.  Also, give a direct argument for the following:
Every graph G with maximum degree Delta can be colored with at most
Delta + 1 colors.  Can you characterize those graphs which require
the upper bound?  (i.e., which graphs only need Delta colors?)

If G is any graph, we call a subset V' of V(G) a cut-set of vertices if G - V' is disconnected or trivial; we call a subset E' of E(G) a cut-set of edges if G - E' is disconnected or trivial. The (vertex-) connectivity of G is defined to be the minimum cardinality of any cut-set of vertices and is denoted by kappa(G) (the text also uses the letter "c" for this invariant. (Cardinality just means the number of elements in a set.)

The edge-connectivity of G is defined to be the minimum cardinality of any cut-set of edges and is denoted by lambda(G).

Recall that delta(G) (lower-case "delta") is the minimum vertex degree of a graph G. E.g., the graph Fig. 108a has kappa = 1, lambda = 1, and delta =3; the path P_5 with 5 vertices has all three of these invariants equal to 1. Any disconnected graph has both kappa and lambda equal to 0.

For Wed., find a short proof for the second inequality below:

For every graph G, kappa(G) <= lambda(G) <= delta(G).

The symbol "<=" means "less than or equal".

You don't need to write this up but do be prepared to either 
put it on the board or to write it down for a quiz.

Also, construct examples of specific graphs (as small as possible)
which achieve all four possible combinations of "<" and "=" above;
e.g., graphs with kappa = lambda = delta, kappa = lambda < delta,
kappa < lambda = delta, and kappa < lambda < delta.  Again, you
need not write these up for collection but you should be ready to
put them up on the board or to write them on a quiz (where notes
will be allowed).  Of course, the graphs I gave above as 
examples aren't permitted as solutions - find your own examples!

For Friday 9/23 for collection as homework, pp. 115--116, #13, 14, 17.

Note: there are two assignments for collection described below. The first was due on Fri. 9/16 and the second on 9/19.

Read the chapter on Euler's formula (you can skip the part on "algebraic topology" for now) and for collection on 9/19 (Monday) - written up as usual do problems 6,8, and 11 on pp. 113--115 (number 11 is mostly a definition but at the very end, the author gives examples and then asks for the connectivity c of certain graphs given earlier.

For Friday 9/16: Read the rest of the chapter on planarity. I suggest you skip the 3 examples just before the problem set.

For Friday 9/16 (HW) do the following problems on pp. 93--94: #7, 9, 10, 13, 14. Hint for #7: Use the hint in the book about how to find an embedded copy of an expansion of K_3,3 (written "UG" in the text) in another graph (see p. 86). Try it for the Petersen graph. These are to collected so please write them up as usual.

Older problems and assignments

For Monday, read pp. 64 -- 80. The term "expansion" in the text is more often called "subdivision"; I'll go over some of this in class on Friday. Do problems 1(a) and (b), 2, and 7 on pp 92--93 and write them up for collection on Mon. 9/12 . I went over the homework and briefly reviewed planarity in class today (Fri) so if you weren't there, check with a classmate to see the notes.

Homework collected on Wed. 9/7 pp. 56--61: 6,15,21,22,38,39.

On this and all subsequent homework, please be sure to (1) write legibly, (2) show your work, and (3) staple the pages together. It is ok to first work things out in a rough way and then rewrite the main conclusions clearly, stapling everything together so I can see how you got there.

Since I did this quickly at the end of class, here's a brief reminder of what I asked you for Friday Sept. 9:

Let G = (V,E) be a graph and define a relation W on V by
(v,w) in W if and only if there exists a _walk_ from v to w.
(A walk from v to w is a sequence which alternates between
vertices and edges, with each edge joining the two vertices
with which it is consecutive, where the first vertex is v and
the second vertex is w.)   This is a reflexive relation since
the sequence v (one term only) satisfies the conditions to be
a walk from v to v.  The relation is also clearly symmetric.

Note that the vertices of a walk need not be distinct and
the edges of a walk can be repeated as well.

Show that the relation W is transitive.  

In class we defined a relation P on V by (v,w) in P iff there is a _path_ from v to w and this is clearly reflexive (path with one vertex) and symmetric. Try to show that P is also transitive by using the idea of a walk ...

So we now know that P and W are actually the same relation! Clearly, the existence of a path implies the existence of a walk (every path is a walk) so P subset W (as relations, i.e., as subsets of V x V. The arguments above (and in class) show that if there is a walk joining v and w, then there is a path joining v and w so also W subset P, and hence W = P (as relations).

The equivalence classes of vertices of G with respect to this relation are called the _components_ (or connected components) of G, and they correspond to what the text calls "pieces" of the graph.

You should have read chapter 2 (on graphs). In addition, to the hw above, try problems 4,7,13,16,20,30-37, and 40, which have answers on pp. 199-200. Of course, it is better to try the problems _before_ looking up the answers.

For Monday, read pp. 64 -- 80. The term "expansion" in the text is more often called "subdivision"; I'll go over some of this in class on Friday.