![[Teaching]](pattern_star.gif)
Graph Theory I [Grafteori I, MM810]
Reexam
The date for the oral reexam is 18.6.2011. Here is a list of the original exam topics.
Course Log / Time Table
Numeric citations refer to the 4th edition of Diestel's book (see below).
| Week | Events | Content |
|---|---|---|
| The Basics. We have treated Sections 1.1, 1.2, 1.3, 1.6, and 1.8. Please work out the proofs of Propositions 1.3.2, 1.4.1, and 1.4.2: The proofs are easy and instructive. Homework is to prepare Exercises 6 and 16 (4th edition!) from Chapter 1 for Wed 2.2.2011 and to read Chapter 1.5 until week 6. You might either present the solutions to the exercises on Wednesday, or hand in your written solutions for correction. | ||
| Matchings, Covering, Packing. We have treated Sections 2.1 (without Theorem 2.1.4) and 2.2 (without Theorem 2.2.3). Homework is to prepare Exercises 1 and 18. We touched the problem of finding a factor H in a graph such that the degree function of H equals some given function f: This can be reduced to finding a 1-factor in some auxilary graph. | ||
| Connectivity. We have treated Proposition 3.1.1, Lemma 3.2.4, and Theorem 3.2.5. Theorem 3.2.4. has been generalized as follows: Suppose that G is a k-connected graph on more than k+1 vertices and x is a vertex such that G/e is not k-connected for every edge e incident with x. Then there exists a separating vertex set S of size k containing x and a neighbor of x such that G-S has a component with less than k/2 vertices. - Convince yourself again that Lemma 3.2.4 follows from this. As homework, prove that it implies that every vertex of a 2-connected graph G on more than 3 vertices is incident with an edge e such that G/e is 2-connected. We considered the second proof of Menger's Theorem 3.3.1, by path extension, and its corollaries 3.3.4 and 3.3.5. More homework: Work out the proof of the global versions, Theorem 3.3.6. | ||
| Planar Graphs. Starting with the definitions of plane and planar graphs, we looked at combinatorial properties of the facial cycles, on which the proof of Kuratowski's Theorem relies. Essentially, these are: In a 2-connected plane graph, the boundary of every region is a cycle (not necessarily induced), whereas in a 3-connected plane graph, the boundary of every region is an induced cycle, and in a plane 2-connected graph, every edge is on the boundary of exactly 2 regions. The rigid proofs of these facts are tedious, and for brevity I have skipped them (they are, however, in the book). Moreover, we have looked at two methods how to reembed a plane graph such that an arbitrary region turns into the unbounded region of the reembedding. We have proved - by double counting, not using Euler's formular - that the two Kuratowski graphs are not planar. We defined minors and subdivisions (see Section 1.7), made a brief excursion to graph minor theory and graphs on higher surfaces, and gave a compact proof of Kuratowski's Theorem (see Section 4.4). This was all quite different from the book proofs, mainly because time was short, but the essential arguments can be found in Sections 4.1, 4.2, and 4.4 as well. Homework: Work out the proofs of Theorem 4.2.9 and Corollary 4.2.10. Use the latter to proof that every planar graph has a 6-coloring, i. e. a function assigning a color out of {1,2,3,4,5,6} to each vertex such that adjacent vertices receive distinct colors. Try to find a procedural description for the fact that H is a topological minor of G, similar to the one in Corollary 1.7.3 (Hint: You might declare some contractions as illegal). | ||
| Vertex Colouring. We treated Theorem 5.1.1 and Proposition 5.1.2, as well as the bounds to the chromatic number obtained from counting edges between color classes (Proposition 5.2.1) and greedy coloring (Proposition 5.2.2). The qualitative statement of Corollary 5.2.3 is that high chromatic number forces a subgraph of high minimum degree. Try to find similar statements in the course where different invariants are involved (such as connectivity and average degree). We treated Brooks' Theorem (Theorem 5.2.4), where the Kempe chains from Proposition 5.1.2 came back. (Recall that an a,b-Kempe-chain in a vertex-colored graph is a component of the subgraph induced by colors a and b. Exchanging the two colors everywhere in such a chain produces a new (properly) colored graph.) | ||
| Hadwiger's Conjecture / Edge Colouring / Extremal Graph Theory. As an addendum to vertex colorings, we have introduced Hadwiger's Conjecture (see introduction section 7.3), one of the most important open questions in Discrete Mathematics. We then treated Vizing's Theorem (Theorem 5.3.2). Note that, again, we used colour exchange - now along the edges of paths - as to modify given edge colorings; this method provides a very simple proof of König's Theorem that the chromatic index of a bipartite graph equals its maximum degree (Proposition 5.3.1). - We then touched part of the material in Chapter 7 on extremal graph theory (Theorem 7.1.1). | ||
| Hamilton Cycles. The two most important open questions in this part of the theory are Chvatal's t-tough-Conjecture that there exists a t such that every t-tough graph is hamiltonian, and Thomassen's Conjecture that every 4-connected line graph is hamiltonian. We treated a number of necessary or sufficient conditions for a graph to be hamiltonian (Section 10.1 except for Theorem 10.1.3) and then turned to Chvatal's theorem on Hamiltonian sequences (Theorem 10.2.1). Observe that Dirac's Theorem (10.1.1) is an immediate consequence of 10.2.1. To find a proof for Corollary 10.2.2 is a good excercise. There are conditions similar to those from Theorem 10.2.1 ensuring degree sequences to be k-connected or (much more difficult) k-edge-connected. |
*: The date (dd.mm.) indicates monday of the respective week.
Contents
Graph theory is a comparatively young area of mathematics, with tight links to both theoretical and applied computer sciences. This introductory course treats a number of classic graph problems and the related theorems, and illustrates that graphs and networks are omnipresent models in science and technology. Although, at this level, graph theory could be considered as a part of general math/cs education, the audience will encounter open research problems soon.
For more intro, see the Wiki article Graph Theory.
Provided that some participants get crazy about graphs and their relatives, I will offer a course Graph Theory II as a follow-up in the 4th quarter, and for those who really cannot get enough of it I have two reading courses on Graph Connectivity Theory and on Matroids in my mind and in my files (as preparation for a master thesis in the beginning of the next academic year).
Literature
The material is covered by the comprehensive textbook
Graph Theory by R. Diestel, 4th edition, Springer-Verlag Heidelberg (2010).
For a free preview version (the entire book for free online viewing, in slow low-quality PDF), as well as for pay versions, see diestel-graph-theory.com. There are paper copies of elder editions (they will suffice), as well as a bunch of further textbooks in the MM810 slot in IMADA's library.
Prerequisites
Basic notions from linear algebra should be known, and basic notions and methods from abstract algebra should have been encountered.