See index page above for summer plans - esp. if before 21 May
Last updated Jan. 11, 2004 Phone 7-2703 (K-C or to leave voicemail) or kainen@georgetown.edu
Today in class we discussed Whitney's theorem: A planar triangulation (i.e., a maximal planar graph) either has a separating triangle or else it must have a spanning cycle (i.e., it is a Hamiltonian graph). A triangle is _separating_ if removing the vertices of the triangle disconnects the triangulation. For instance, if you have any triangulation with at least 4 vertices, you can extend it to a larger graph which is a triangulation with a separating triangle by simply putting a new vertex v in the middle of any triangular face abc and connecting v to each of the vertices a,b,c by an edge. Then removing a,b,c produces one connected component consisting of v and at least one additional component.
Now suppose that we are interested in 4-coloring the vertices of all possible planar triangulations (this is the "Four Color Problem" since if you can 4-color maximal planar graphs, you can do them all ;-) A minimum-vertex counterexample (if one existed) could not have a separating triangle. Why?
For Monday, April 22, I asked some of you to rewrite the second quiz but everyone ought to try it. Here is a sketch of what you should be ready to explain on Monday: We can define a natural function phi from the set 2^E(G coprod H) to 2^{E(G)} x 2^{E(H)} by phi(F) = (F intersect E(G), F intersect E(H)), where F is any element of the powerset of the edges in the coproduct of G and H. (The notation 2^A for the powerset of a set A, i.e., the set of all of its subsets, comes from replacing a subset by its characteristic function.) I won't define the technical sense of ``natural'' but you should check that in particular phi is both 1-1 and onto; these are immediate once you realize that E(G coproduct H) = E(G) coproduct E(H), and coproduct means disjoint union of graphs or of sets.
Now for any graph G let PM(G) denote the set of all perfect matchings in G - so the cardinality of PM(G) is pm(G). Of course, PM(G) is a subset of 2^{E(G)}. Show that phi(PM(G coproduct H)) = PM(G) x PM(H). Why does this suffice?
For Wed., Apr. 17, think about your proof in problem 1 below that a_3(T) = upper-floor(Delta(T)/3) where T is a tree and Delta(T) is its maximum degree. Have you justified things clearly? Is your argument extendable to arbitrary positive integer values of k replacing 3?
Similarly, compare your argument for chi + chi-bar <= n+1 to the one I gave out in xerox copy.
Here is the take-home:
(1) Let a_3(G) be the smallest integer k such that
E(G) = F_1 + F_2 + ... + F_k,
with G(F_j) a forest having maximum degree 3, for 1 <= j <= k;
it is easy to check that with 3 replaced by 2, this would be the
definition of linear arboricity. Clearly, a_3(G) is at least
the upper-floor of Delta(G)/3 since each forest can use up at
most three edges at any vertex. Formulate a conjecture for
the value of a_3(T) when T is a tree and try to prove your conjecture.
(2) How many perfect matchings does the Petersen graph have?
You can look up the Petersen graph in our text; the homework
exercise similar to this was to count the number of perfect
matchings in Q_3, the 3-dimensional cube. I showed in class
that this number is 9, and the argument will be helpful below.
Note that a perfect matching is a subgraph of a given graph,
so the number of perfect matchings counts distinct subgraphs
(we count them as distinct if the subgraphs are different).
(3)
Show that the number of perfect matchings in Q_k is at least
2^{2^{k-2}}, for k at least 2. This formula says that Q_2 is
at least 2^1 = 2, which is correct, and that Q_3 has at least
4 (we know it actually has 9). Use induction on k. Hint: THis
one depends on the idea of building up some matchings of Q_k
from matchings of Q_{k-1} and also on the arithmetic of exponents.
It's easier than the other induction problem from the homework
collected Monday the 8th.
(4)
Problem 3.1.18 of section 3.1.
I forgot to list the two problems I collected today (April 8) so if you missed them, they were (i) count the matchings in the 3-dim'l cube and (ii) show that chi(G) + chi(G-bar) <= n+1, where G has n vertices, G-bar denotes the complementary graph, and chi denotes chromatic number.
*** flash *** We have a computer and lab space in Kober-Cogan B06. Also, there is now a laser-imaging system ;-) My office hours are now extended to MWF morning and TTh afternoon in K-C in B04/06; see the index page for details. ****************
See a new page (thanks to Jack Dempsey)
If you are thinking about a course for Fall 2002, there is some information on the Combinatorics Course on the index page above.
For Monday March 25, go over problems 5, 8 and 9 to be ready for a possible quiz! Hint for #5: chi(G) is at most Delta(G) + 1. Now use the fact that in a coloring, each class of same-color vertices constitutes an independent set! Oh, I guess you should know how to do #4 also. (If you weren't in class today, ask one of those who were for the notes!) For Wed. Mar. 26, look at p 211 in the text which shows how the Konig-Egervary theorem can be applied to some seemingly rather unrelated problems; you will need to use the index of the book to look up a couple of terms and results.
For Wed. April 3, finish the proof of Dirac's theorem (and the lemma) on p. 211.
For Wed. March 20, please do the problems below for handing in. That's 2 through 9 excluding 7 of section 3.1.
James had some questions about the underlying material and likely many others do, too, so I'll postpone the homework above till Friday. But do read the material in the text so that we can discuss it in class on Wed. Here's a separate (and amusing ;-) problem: What is the next term in the sequence chi'(G), la(G), ... ? Here chi'(G) is the least number of colors needed for the edges so that no two edges of the same color have a common endpoint. Note tha la(G) can be viewed as the least number of colors needed for the edges so that no two monochromatic paths have a common endpoint. View each of these as the minimum number of forests into which G can be decomposed, where the forests have to satisfy suitable constraints.
Let G be a graph. A decomposition G = G_1 + ... + G_t is a list of spanning subgraphs which are pairwise edge-disjoint. The number t is called the length of the decomposition. We may consider the problem of choosing such a decomposition subject to conditions on the graphs G_i. A linear forest is a graph which is the union of a vertex-disjoint family of paths. Equivalently, a linear forest is a forest for which each connected component is a path. Since isolated points are paths of length 0, we can always suppose a linear forest is spanning. The linear arboricity la(G) of a graph G is the smallest number t such that G has a decomposition into linear forests.
Exercise 1 : Find a lower bound on la(G) in terms of the maximum degree Delta(G) of the graph G. Exercise 2 : Determine la(T) when T is a tree. At least, try to make a conjecture!
warning *** material ahead is intended as a challenge to students and should be avoided unless you want to work hard. I won't ask about it (I think ;-) on tests but will be curious to see if anyone decides to dive in anyway. As a device to avoid the horrible new circumlocutions attaching to the third person in narrative flow, I've decided to use "it" as the reader may indeed someday soon be an AI which could have personality aspects without any gender assumption at all (but we shall find it hard to step over body-centered metaphors). ***
Let us take the following point of view. A graph must be computed; that is, a particular computation must be carried out for each edge in the graph. It might depend on which order is used. We allow the existence of a path-processor which can carry out a sequence of computations in a portion of a path up to some given length tau. For simplicity, suppose tau is 1.
For any linear forest H, we can define two geometric parameters that intuitively describe computational requirements: The width w(H) of the forest is the number of nontrivial components - i.e., the number of connected components of H \ {isolated points}. This gives a lower bound on the number of path-processors required to implement the computation. Also, we can take the length l(H) of a linear forest as a function of the lengths of its components - distinguishing especially the L_1, L_2 and L_{oo} norms obtained by either summing, square-rooting the sum of squares, or maximizing, resp. For now, we focus on L_{oo} and invite the reader to work out the L_1 and L_2 cases for itself.
Suppose that a path-processor can only handle tau steps along the path in a time-frame. Signal moves across each edge only when its turn has come in the particular path-processor segment. If l(H) measured in L_{oo} norm satisfies UF(l(H)/tau) = u, then the entire graph H can be computed using at most u * w(H) path-processors.
If G is decomposed into t linear forests, with r_i nontrivial components for the i-th linear forest G_i, 1 <= i <= t, then, putting w = max w(G_i) = max r_i and l = max l(G_i), clearly |OPT(G)| <= w * l, where |OPT(G)| denotes the result of the best possible arrangement of edges in G into linear forests that minimizes number of path-processors required. In fact, it is also clear that even if we minimize over all possible partitions of edges into linear forests (not just those achieving a minimum number of linear forests) the minimum number of processors used cannot be below m/tau which would itself be unlikely to hold due to the rarity of no round-off error.
I think there are a couple of interesting theorems in this direction and will be glad to provide advice to any interested student.
*** end of digression Dr. Chang will teach the two classes immediately following the Spring break, on March 11,13; there may be a quiz! Read the first section of Chapter 3 and do problems 2,4,5,6,8 and 9 on p.118.
For Friday, (1) remember to bring the homework (which I forgot to collect today ;-) and (2) see if you can find the ``forbidden subgraphs'' which characterize outerplanar graphs. Recall that today I asserted that G is planar if and only if G has no subgraph homeomorphic to K_5 or K_3,3. That is, K_5 and K_3,3 are the forbidden subgraphs characterizing planarity.
Two graphs are _homeomorphic_ if and only if they have isomorphic subdivisions. A _subdivision_ of a graph is determined by subdividing each of its edges any finite nonnegative number of times. (Thus, two graphs are homeomorphic if they are the same up to vertices of degree 2.) For instance, any two cycles are homeomorphic and any two (nontrivial) paths are homeomorphic, but a cycle is never homeomorphic to a path since a path always contains a vertex of degree at most 1 but a cycle has no such vertex (introducing new vertices of degree two can't make them isomorphic since the vertices of degree at most 1 are unaffected). Since even-length cycles are 2-colorable while odd-length cycles need 3 colors, homeomorphic graphs can have different chromatic numbers.
Check your understanding by showing that any graph is homeomorphic to a bipartite graph!
We defined chromatic number chi and clique number omega for graphs and also gave the definition of the disjoint union and the join of graphs (see the text also). I asked you to show: (1) the chromatic number of H is at most that of G when H is a subgraph of G, and (2)(a) f(G disjoint union H) = max (f(G), f(H)) and (b) f(G join H) = f(G) + f(H); where f is either chi or omega. These will be collected on Wed. the 20th.
A plane graph is a graph which is actually embedded in the plane so that each vertex corresponds to a point and each edge to a simple closed curve (or straight-line segment if you prefer) joining the points corresponding to its endpoints. The complement of a plane graph is a disjoint union of connected components which are called the _regions_ of the plane graph. For instance, K_4 has exactly four regions. The boundary of a region R is the set of edges e for which any point on the curve C corresponding to e has the property that it has distance 0 to the region - i.e., there is a sequence of points in the region which converge to the point. A graph is planar if it is isomorphic to a plane graph. It follows from the next theorem that the number of regions in any plane graph isomorphic to a planar graph is well-defined. Euler's formula: Theorem: If G is a connected plane graph, then n - m + r = 2, where n,m,r are the numbers of vertices, edges and regions, respectively. Proof. The result holds if r = 1 because for trees n - m = 1. We proceed by induction on r. Let G be a connected plane graph with n,m,r vertices, edges and regions, resp., where r > 1. There must exist an edge e in E(G) for which G - e is connected (otherwise G would be a tree but r > 1). Such an edge e must lie on the boundary of two regions. Hence, G - e has one fewer region than G and one fewer edge. The inductive hypothesis says that n - (m - 1) + (r - 1) = 2 so by cancelling the 1s, we get Euler's formula for G. Corollary: If G is a planar graph with n vertices and m edges, then (for n geq 3) m leq 3(n-2). Proof. First note that the restriction is necessary - else K_n, n = 1,2 are counterexamples. Second, it suffices to prove the result for connected graphs. Third, the result holds for trees. We proceed by induction on the number of cut edges in G. The basis case is no cut edges. Let H be some specific plane embedding of G (possible since we assume G is planar) and let n,m,r be the numbers of vertices, edges and regions in H (since H is isomorphic to G, it has the same number of vertices and edges). Since G has no cut edges, every edge in H lies on the boundary of exactly two regions. Hence, if alpha is the average number of sides in the boundary of a region, then r*alpha = 2*m. Rewriting Euler's formula as m - r = n - 2, multiplying through by alpha, and doing the algebra, we get (*) m = (alpha/(alpha - 2))(n - 2). Since alpha geq 3, m leq 3(n-2). Now suppose we know the result holds for k cut edges and let H have k+1 cut edges, with n vertices, m edges and r regions. Choose a cut edge e of H and let H' = H / e be the graph obtained from H by _shrinking_ the edge e to a single point. This does not increase the number of cut edges remaining so H' has k cut edges. Also, H' is plane and has n-1 vertices and m-1 edges. Hence, by the inductive hypothesis, m-1 leq 3(n-1-2) = 3n-9. Therefore, m leq 3n-8 < 3n-6 so the result holds.
In class and for homework, we saw that m leq 3(n-2) implies that the average degree is less than 6 (for a planar graph) and hence there must always be a vertex of degree not exceeding 5 (else, if all vertices have degree exceeding 6, the average would too). Similarly, for graphs in the _torus_ (think "doughnut" or "inner tube") n-m+r = 0 and the corresponding upper bound on edges is m leq 3n; hence, average degree is at most 6 and so there must be a vertex of degree not exceeding 6 in any toroidal graph.
For homework for Wed. I asked you to do the same thing for the case of "outerplanar" graphs - which are graphs isomorphic to plane graphs with the additional property that every vertex lies on the boundary of a single region. Equivalently, an outerplanar graph is a graph which is isomorphic to any subgraph of a polygon with noncrossing inner diagonals.
Ok, now we know that an FSM digraph (which is a digraph with out-degree equal to one at every vertex) is characterized by the fact that every connected component of the underlying graph consists of a cycle and a set of trees each intersecting the cycle in a unique vertex for each tree. The orientation of D ensures that the unique path from any vertex of the trees to the corresponding "root" on the cycle is directed from the vertex to the root, and the trees constitute the transient component of the FSM. The cycle constitutes the steady-state part since all vertices (i.e., states) in the cycle repeat endlessly.
I showed in class that the consequences Euler's formula can be strengthened, but just using the basic version: m \leq 3(n-2), show that any planar graph must have average degree strictly less than 6, and hence it must have some vertex with degree at most 5. Write this up for Monday. Also, Test 1 (rewrite as needed) is due on Monday and I'll return your papers and give you the answers. I mentioned in class that "distinct" means "different", while "disjoint" can occur in two ways: edge-disjoint if no edges are shared and vertex-disjoint if no vertices (and hence no edges) are shared. For spanning trees, we are only interested in them as subgraphs so the ordering of their edges and vertices doesn't matter.
For the 8th, in addition to completing or fixing anything from the test that you weren't sure of, and reading over the proof of Euler's formula that I sketched, try the following very nice problem: Find the structure of a digraph in which every vertex has a unique arrow pointing away - i.e., in which every vertex has "outdegree" equal to 1. Use the text (and its index) as a resource to find some background reading!
Make sure you could prove, e.g., that removing an endpoint from a connected graph leaves a subgraph which is still connected. We'll review the homework and some related problems in class on Monday to prepare for the test Tues. night (at 7:30 pm in ICC 211A).
Also try 1.2.10(b), 1.2.20 (hint: the problem's conclusion is much too modest; in fact, something much stronger is true and sometimes stronger statements are easier to prove ;-), 1.2.22, 1.3.14.
For Wed., here are some problems to be ready to do in class. Prove or disprove: Every forest is bipartite (a forest is a graph for which each connected component is a tree). Hint: use a characterization of bipartite graphs given as 1.2.18. This gives an "existential" proof. Can you find a constructive one? Some additional problems: 1.2 #8,11,18,24. Also, 1.3 #5.
For Mon. 28 Jan., read 1.3 in the text. I'll add some problems here shortly. Also, check that my handwaving about just adding edges subject to not making a cycle must produce a spanning tree eventually ... and ditto for the argument about going from a cycle decomposition to an Eulerian circuit.
For Friday the 25th, remember the Lemma we developed for trees: If T is a tree and v is an endpoint of T, then T-v is also a tree. We need a comparable lemma for "even" graphs. A graph is even if every vertex has even degree. Lemma: If G is even and v \in V(G), then there exists a cycle in G through v. We'll prove this on Friday. Meanwhile, however, use the Lemma to prove the following which is to be handed in on Friday: Thm. If G is even, then G has a cycle decomposition (i.e., there is a family of cycles in G such that every edge belongs to one and only one cycle in the family). Proof sketch: Use induction on the maximum degree (capital Delta(G)). If Delta(G)=0, trivial (the family is empty since there are no edges ;-) To prove the induction step, use induction on the number t of vertices of G which achieve the maximum degree. The basis case (for this second or "inner" induction) is t=1. So we want to show that an even graph with maximum degree Delta(G) achieved at exactly one vertex v has a cycle decomposition. Use the Lemma and the inductive hypothesis for the outer induction. Now, to complete the proof for the inner induction, once again use the lemma and now use the inductive hypothesis related to the inner induction.
For Wed. Jan. 23, read the rest of section 1.2. Does the Petersen have an Eulerian circuit? (Hint: This is a "who's buried in Grant's Tomb" problem. ;-)
Notice the very useful Lemma 1.2.25: If every vertex of a graph has degree at least two, then the graph contains a cycle. Definition: A connected graph is a tree if it contains no cycles. As a corollary of this Lemma, a nontrivial tree must contain at least one vertex of degree 1 (called an endpoint). Indeed, if all vertices have degree 2 or more, there is a cycle. By nontriviality and connectedness, no vertex has degree 0. (In fact, for a nontrivial tree, there must actually be at least _two_ endpoints. For if one begins at the first endpoint and follows a maximum length path, by finiteness of the number of vertices, the path ends and this other end of the path must also be of degree one else the path could be extended.)
Exercise (to be handed in on Wed. the 23rd). Use induction on the number of vertices to show that for every tree, the number of vertices minus the number of edges is 1. You'll need to use the above remark that every nontrivial tree contains an endpoint to make the inductive step!
For those who are inductively challenged, I'll be around on Sunday late afternoon and Monday late afternoon and for office hours on Tuesday as well.
If you are feeling energetic, look up the definition of a simplicial complex and see that graphs are 1-dimensional simplicial complexes. A 2-dimensional simplicial complex also has 2-simplexes which are determined by 3-element subsets of the vertices (i.e., 2-simplexes are to edges as 3 is to 2). The result below can be extended to prove that every 2-dimensional simplicial complex can be embedded in 5-dimensional space. Why are 5 dimensions (rather than, say, 4) necessary? This is _not_ an exercise for graph theory but some of you may find it interesting anyway ;-)
For Jan. 18, prove that for any positive integer n, there exists a set of n points in 3-dimensional space in _general position_ i.e., (i) no three on a line (ii) no four in the same plane. Use induction on n. As a corollary, check that any finite graph can be embedded in 3-space so that (1) vertices correspond to a set of distinct points, (2) edges correspond to straight-line segments joining the corresponding pair of points, (3) none of the segments intersects a vertex-point except for its endpoints, and (4) no two of the segments intersect except at a common vertex. The claim (i) is used for (3) and (ii) for (4). The emphasis in your write-up should be on the existence of the general position realization for any finite set of points in 3-space. To do so, you'll need to think about how much "room" there is in space to accomodate lines and planes. For that part, you can make some reasonable geometric hypotheses but be sure to state them clearly!
Homework for Wed. Jan. 16: Let G = (V,E) be a graph and suppose we define, for any two vertices u and v, a function d(u,v) = the length of a shortest u-v-path. Show that d(u,v) is a metric on the set of vertices of G; that is,
(i)d(u,v) is nonnegative and d(u,v) = 0 if and only if u = v (for all u,v); (ii) d(u,v) = d(v,u) (for all u,v); and (iii) d(u,w) is less than or equal to d(u,v) + d(v,w) (for all u,v,w).Lemma 1.2.5 is needed for (iii).
For Mon. Jan. 14, section 1.2 up to but not including Eulerian circuits. Don't worry about the fussy description of induction; you'll get the idea better when we use induction in examples. Meanwhile, you might brush up by seeing if you can prove, by induction on n, that the sum of the first n positive integers is (n+1)n/2. We covered problems 1.1.3,4,5 and 6 in class - a subset of 1.1.7,8,37,38 will be covered Monday. Also on Monday we will go over some of 1.2.2,4,6,7; maybe there will also be a quiz ;-) For Wed. I'll assign a couple of the homework problems to be written up for collection.
For Friday Jan. 11, read section 1.1 skipping the paragraphs marked * except for 1.1.41 and 1.1.42. On p.15 and following, try exercises 3,4,5,7,8,37,38. Remember that quizzes and class participation (and homework when I assign it for collection) are a significant factor in grades, not to mention learning the subject!
Back to the index page To contact me, you can use voice mail (202-687-2703), e-mail kainen@georgetown.edu or just click e-mail