Math 582, Section F1 - Class Log
- 1. Monday, 08/23:
Handed out basic info about the class.
Introduction. Started counting spanning trees in complete graphs.
Examples.
Proved a generalization of Cayley's Formula (Theorem 1.1, Theorem 6.1.18 in the book).
Introduced and gave an example of Prufer codes. Proved properties of Prufer Algorithm.
Stated the claim on Prufer codes (Theorem 1.2).
- 2. Wednesday, 08/25:
Proved Theorem 1.2 on Prufer codes and gave an example.
Stated,
gave an example and almost proved the Matrix Tree Theorem
(Theorem 1.3, Theorem 6.1.26 in the book).
- 3. Friday, 08/27:
Finished proof of the Matrix Tree Theorem
(Theorem 1.3, Theorem 6.1.26 in the book).
Stated and
discussed (but did not prove) the Directed Matrix Tree Theorem (Theorem 1.6, Theorem 6.1.28 in the book).
Examples. Stated the Matrix Arborescence Theorem (Theorem 1.7, Theorem 6.1.30 in the book).
Showed how
Directed Matrix Tree Theorem follows from
the Matrix Arborescence Theorem. An example. Started to prove Theorem 1.7.
- 4. Monday, 08/30:
Proved the Matrix Arborescence Theorem (Theorem 1.7, Theorem 6.1.30 in the book).
Counting Eulerian circuits in directed graphs, an example.
A lemma (Lemma 1.8, Lemma 6.1.33 in the book) on last edges exiting
vertices in Eulerian circuits.
Lemma on connections between spanning in-trees and Eulerian circuits
in directed graphs.
Proved BEST Theorem (Theorem 1.10, Theorem 6.1.36 in the book) on the number of Eulerian
circuits in digraphs and spanning in-trees. Two corollaries.
- 5. Wednesday, 09/01:
Graph decompositions.
Ringel's conjecture on tree-decompositions
of complete graphs. Defined graceful labelings of graphs.
Examples of graceful graphs. A discussion of
the Graceful Tree Conjecture. Proved Theorem 1.13 on decompositions
of complete graphs into copies of graphs with graceful labelings.
Caterpillars have graceful labelings.
Stated Wilson's Theorem (Theorem 1.14) on decompositions of large complete graphs into
copies of the same graph.
On decompositions of 2m-regular graphs into m-edge trees.
Graham-Haggkvist Conjectures. Stated
Theorem 1.15 on decompositions of 2m-regular graphs into m-edge trees.
- 6. Monday, 01/28:
Proved
Theorem 1.15 on decompositions of 2m-regular graphs into m-edge trees.
Gyarfas-Lehel Conjecture on decomposition of the complete n-vertex into given set of trees
of different sizes.
Packing of graphs: definitions and examples.
Some graph-theoretic
problems and results
in the language of packing. Proved Sauer-Spencer
Theorem (Theorem 1.16) on packing of graphs with bounded product of
sizes.
- 7. Wednesday, 09/08:
Proved Sauer-Spencer
Theorem (Theorem 1.17) on packing of graphs with bounded products of
maximum degrees. Some extremal results and
conjectures on packing of graphs.
A short discussion of Bollobas-Eldridge Conjecture of graph packing.
Equitable colorings of graphs: properties and examples.
Stated, discussed and started to prove
the Hajnal-Szemeredi Theorem on
equitable (r+1)-coloring of graphs with maximum degree at most r.
- 8. Friday, 09/10:
Delivered the main part of the proof of the Hajnal-Szemeredi Theorem on
equitable (r+1)-coloring of graphs with maximum degree at most r.
- 9. Monday, 09/13:
Finished the proof of the Hajnal-Szemeredi Theorem.
Discussed the Chen-Lih-Wu Conjecture on equtable colorings of
graphs.
Started Section 2 on vertex degrees.
Stated Erdos-Gallai Theorem (Theorem 1.19) on graphic sequences. Stated the Havel-Hakimi Theorem (Theorem 1.20) on such sequences.
- 10. Wednesday, 09/15:
Proved the Havel-Hakimi Theorem (Theorem 1.20) on graphic sequences.
An example of applications.
Discussed
graphs with the same degree sequence. Proved Theorem 1.21 on 2-switches.
Stated and half-proved
Edmonds' Theorem on potentially k-edge-connected
sequences (Theorem 1.22).
- 11. Friday, 09/17:
Finished the proof of Edmonds' Theorem on potentially k-edge-connected
sequences (Theorem 1.22). Vertex partitions. Stated and proved
Lovasz' Theorem on partitions with bounded maximum degree (Theorem 1.23).
A conjecture on the topic by Correa, Havet and Sereni. Stated and proved a
Theorem of Stiebitz on partitions with bounded minimum degree (Theorem 1.24).
- 12. Monday, 09/20:
Introduction into the Reconstruction Problem. Definitions and
notation. An example.
Kelly's Lemma (Theorem 2.1). Regular graphs are reconstructible,
Proved Theorem 2.2 that
disconnected graphs with at least 3 vertices are reconstructible and
stated
Theorem 2.4
that every tree with at least 3 vertices is reconstructible.
- 13. Wednesday, 09/22: Proved
Lemma 2.3 and Theorem 2.4
that every tree with at least 3 vertices is reconstructible.
- 14. Friday, 09/24:
Proved
Tutte's Theorem (Theorem 2.5) on reconstructibility of the number
of some spanning subgraphs of a graph.
Applications: the number of spanning
trees and the number of hamiltonian cycles in a graph are reconstructible.
Started edge-reconstruction: definitions, stated Harary's Edge-Reconstruction
Conjecture.
- 15. Monday, 09/27:
Stated and hinted the proof of
edge-Kelly
Lemma (Lemma 2.7). Stated and proved Lovasz' Theorem (Theorem 2.7) on
edge-reconstruction of graphs with many edges.
Stated
Nash-Williams' Theorem (Theorem 2.8) and derived from it
Corollary 2.9 by Mueller
that each n-vertex graph with at least 1+log(n!) edges
is edge-reconstructible.
- 16. Wednesday, 09/29:
Proved Nash-Williams' Theorem (Theorem 2.8).
Connectivity: initial discussion. Stated definitions and Menger's Theorems.
Stated and started to prove Edmonds' Branching Theorem (Theorem 3.1).
- 17. Friday, 10/01:
Proved Edmonds' Branching Theorem (Theorem 3.1).
Stated and proved Corollary 3.2 of the Edmonds' Branching Theorem.
Also proved
Theorem 3.3 that Theorem 3.1 implies the edge version of Menger's Theorem
for digraphs.
- 18. Monday, 10/04:
A discussion of dicuts in digraphs. Stated and proved the Lucchesi-Younger
Theorem (Theorem 3.5) that the minimum number of edges covering all dicuts in digraphs with connected underlying graphs equals the maximum number of edge disjoint dicuts module Lovasz' Lemma (Lemma 3.4) on dicuts covering
each edge at most twice. Stated and started to prove Lemma 3.4.
- 19. Wednesday, 10/06:
Guest lecture by Prof. West on graph reconstruction.
- 20. Friday, 10/08:
Proved Lovasz' Lemma (Lemma 3.4) on dicuts covering each edge at most twice.
A short discussion of 2-linked graphs.
Defined k-linked graphs and presented an example of a 5-connected graph that is not 2-linked.
- 21. Monday, 10/11:
Proved that the linkage number of any k-connected graph is at most (k+1)/2.
Considered an example of a 3s-connected graph with linkage number s.
Stated and proved a theorem (Theorem 3.6) by Mader-Thomassen on
subdivisions of graphs with high minimum degree and the
corresponding lemma (Lemma 3.7) on
special partitions of graphs with a given minimum degree.
Discussed
bounds on h(k) - the minimum t such that each
graph with minimum degree t has a subdivision of the complete
graph with k vertices.
- 22. Wednesday, 10/13:
Additional discussion of
bounds on h(k) - the minimum t such that each
graph with minimum degree t has a subdivision of the complete
graph with k vertices.
Proved Theorem 3.8 by Jung and Larman-Many
that graphs with high connectivity are k-linked.
There are (3k-3)-connected graphs that are
not k-linked.
A discussion of
H-linked graphs and their properties. Stated Theorem 3.9 that every
graph with average degree greater than 4k-4 has a k-connected
subgraph.
- 23. Friday, 10/15:
Proved Theorem 3.9 that every
graph with average degree greater than 4k-4 has a k-connected
subgraph.
Stated and discussed Mader's Conjecture on the topic.
- 24. Monday, 10/18:
Recalled ear decomposition of graphs and the theorem
that a graph is 2-connected if and only if it
has an ear decomposition. Recalled Expansion Lemma.
Vertex k-splits.
Proved Lemma 3.10 that vertex k-splits of k-connected graphs are k-connected.
Stated and proved Lemma 3.11 (Contraction Lemma) on 3-contractible edges in
3-connected graphs and
Tutte-Thomassen's
characterization of 3-connected graphs (Theorem 3.12).
A discussion and examples of minimally k-connected graphs.
Stated Mader's Theorem on minimally k-connected graphs
(Theorem 3.13).
- 25. Wednesday, 10/20:
Proved Lemma 3.14 on connectivity of graphs after deleting or contracting
edges. Stated and proved two more lemmas on neighborhoods of 3-vertices in minimally
3-connected graphs.
- 26. Friday, 10/22:
Lecture by Bob Krueger refereeing Mader's proof of his conjecture on k-connected subgraphs of dense graphs for
k<7.
- 27. Monday, 10/25:
Proved Tutte's characterization of 3-connected graphs in terms
of disjoint 3-splits and edge-additions (Theorem 3.17).
Proved Mader's theorem on
vertices of degree k in minimally-k-edge-connected multigraphs (Theorem 3.18).
Stated Mader's lemma (Lemma 3.19) on edge cuts in
minimally-k-edge-connected graphs.
- 28. Wednesday, 10/27:
Proved Mader's Theorem on many vertices of degree k in minimally k-connected graphs
(Theorem 3.13) modulo Lemma 3.19.
Derived from Mader's Theorem a bound (by Bollobas)
on the number of vertices of degree k in a
minimally k-connected graph with n vertices (Corollary 3.20).
Proved Lemma 3.19. Defined relative connectivity.
- 29. Friday, 10/29:
Defined shortcuts. Stated the Shortcut Lemma (Lemma 3.22).
Stated and proved the Orientation Theorem of Nash-Willians (Theorem 3.21) modulo
the Shortcut Lemma (Lemma 3.22).
Almost proved the Shortcut Lemma.
- 30. Monday, 11/01:
Proved Claim 4, thus finishing the Shortcut Lemma.
Stated and briefly discussed the theorem by Gyori and Lovasz (Theorem 3.23) on
k-connected graphs.
Graph drawings, plane and planar graphs. Dual graphs. Euler's Formula
(Theorem 4.2).
- 31. Wednesday, 11/03:
Inequalities for the number of edges in planar graphs.
Graphs K_5 and K_{3,3} are not planar.
For proving Kuratowski's Theorem (Theorem 4.5), proved the following facts:
a) Lemma 4.6 that
contractions of graphs not
containing Kuratowski subgraphs also do not contain
Kuratowski subgraphs, b) Lemma 4.8 that a vertex minimal counter-example to Theorem 4.5
must be 3-connected and c)
Tutte's Theorem that
every 3-connected graph with no Kuratowski subgraph has
a convex embedding in the plane such that no three vertices
belong to a line (Theorem 4.7).
- 32. Friday, 11/05:
Derived from Kuratowski's Theorem and commented Wagner's Theorem
(Theorem 4.9).
The cycle space and the bond space of
a graph; their properties (Theorem 4.10).
Stated and almost proved the planarity criterion due to MacLane:
a graph is planar if and only if its cycle space has a 2-basis (Theorem 4.11).
- 33. Monday, 11/08:
Finished a proof of Theorem 4.11 by proving the last claim.
Abstract dual to a graph. Stated
and proved
a criterion due to
Whitney: a 2-connected graph is planar if and only if it has an abstract dual (Theorem 4.12).
Started Schnyder labelings: definitions and examples.
Simple properties of Schnyder labelings. Lemma 4.13 on labelings of the external vertices in
triangulations. Lemma 4.14: If a is an external vertex in
a triangulation with at least 4 vertices, then a has an internal neighbor u such that
the edge au is contractible.
- 34. Wednesday, 11/10:
Stated and proved Theorem 4.15 on the
existence of Schnyder labelings.
Every Schnyder labeling of
a triangulation is
obtained from a labeling of a smaller triangulation in a simple way (Lemma 4.1).
Stated and proved Uniform Angle Lemma (Theorem 4.17).
Further properties of Schnyder labelings. Partitions of edges of
planar graphs into 3 forests (Theorem 4.18).
- 35. Friday, 11/12:
Lecture by Mina Nahvi on graph reconstruction.
- 36. Monday, 11/15:
A lemma on regions R_i(v)
(Lemma 4.19).
Barycentric representations of graphs.
Straight-line embeddings of
planar graphs into grids of reasonable size using Schnyder labelings.
- 37. Wednesday, 11/17:
Modified straight-line embeddings of
planar graphs into grids of reasonable size using Schnyder labelings.
Started separators in planar graphs. Two lemmas.
Stated and started to prove the
Lipton-Tarjan Theorem on small separators in planar
graphs (Theorem 4.24).
- 38. Friday, 11/19:
Proved the
Lipton-Tarjan Theorem on small separators in planar
graphs (a proof by Alon-Seymour-Thomas) (Theorem 4.24).
A discussion of the Four Color Theorem. Some words on
discharging. A short discussion of light triangles in planar graphs.
- 39. Monday, 11/29:
Stated and proved Borodin's Theorem (Theorem 4.25) on light triangles in normal
planar maps with minimum degree 5. Stated and very briefly discussed
Grotschz's Theorem that every planar triangle-free graph is
3-colorable. Steinberg's
Conjecture.
- 40. Wednesday, 12/01:
A discussion of Steinberg's
Conjecture. Stated and proved a lemma (Lemma 4.27) on structure of plane graphs.
Using this lemma, proved a theorem by Borodin, Sanders
and Zhao (Theorem 4.28) that every planar graph with no cycles of length
4, 5, 6, 7, 8, and 9 is 3-colorable. Started hamiltonian and longest cycles.
Stated Dirac's Theorem (Theorem 5.1) and discussed its sharpness.
- 41. Friday, 12/03:
Presented two proofs of the theorem by Dirac (Theorem 5.1).
Proved a theorem by Ore (Theorem 5.2) and a theorem by Posa (Theorem 5.3) on
the subject.
Derived Corollary 5.4 on hamiltonian-connected graphs and Corollary 5.5 on adding an edge xy when d(x)+d(y)>n-1. Introduced n-closures.
Stated a theorem by Chvatal (Theorem 5.6) on degree sequences guaranteeing existence of hamiltonian cycles
and showed an extremal example for it.
- 42. Monday, 12/06:
Proved a theorem by Chvatal (Theorem 5.6). Proved
Chvatal-Erdos (Theorem 5.7) on Hamiltonian cycles in graphs with connectivity at least the independence number.
Started longest cycles.
Stated Erdos-Gallai Theorem (Theorems 5.8)
on long paths and cycles in graphs with given number of vertices and edges.
Showed how the part on cycles implies the part on paths. Stated a lemma by Kopylov (Lemma 5.10).
Stated and started to prove Kopylov's Theorem on the maximum number of edges in n-vertex
2-connected graphs with no cycles of length at least k (Theorem 5.9).
- 43. Wednesday, 12/08:
Proved Kopylov's Theorem on the maximum number of edges in n-vertex
2-connected graphs with no cycles of length at least k.
Review of the course.
Last changed on December 08, 2021.