Class Log
- 1. Wednesday, 01/17:
Discussed logistics of the course and safety.
Basic definitions: adjacent, incident, neighbors, loops,
multiple edges, simple graphs. Konigsberg bridges.
Examples and more definitions: paths, cycles, complete graphs.
Job Assignment Problem. Examples and more definitions:
bipartite graphs, complete bipartite graphs;
complements of simple graphs, subgraphs and induced subgraphs.
Walks, trails, paths, cycles: definitions and examples.
- 2. Friday, 01/19:
The notions of trails and independent sets, examples.
Defined the order and size of graphs, neighborhoods, notation for vertex degree,
maximum and minimum degrees in a graph, k-regular graphs.
Representations of graphs: drawing, set of rules. Defined Petersen graph.
Defined n-dimensional unit cubes, examples.
Representations of graphs: incidence matrices, adjacency matrices,
lists of neighbors. Examples.
A definition of isomorphism of graphs.
Examples and comments for graph isomorphism.
- 3. Monday, 01/22:
Repeated definitions of walks, trails, paths and cycles.
Stated and proved Lemma 1.1 (1.2.5 in the book) on walks and paths.
A digression on induction.
Using Lemma 1.1, defined the equivalence relation "to be connected by a path"
for pairs of vertices in a graph. Using this, defined
connected graphs and connected components. Proved an observation that
each graph with minimum degree at least 2 has a cycle and that all 2-regular connected graphs are cycles.
Odd cycles are not bipartite.
Stated and discussed
Lemma 1.2 (1.2.15 in the book) on odd closed walks.
Stated and proved Theorem 1.3 ( 1.2.18 in the book)
characterizing bipartite graphs (also called Konig's Theorem).
Stated and proved Degree Sum Formula (Theorem 1.4).
Presented a proof of Lemma 1.2 (1.2.15 in the book) on odd closed walks.
- 4. Wednesday, 01/24:
Repeated a proof of Lemma 1.2 (1.2.15 in the book) on odd closed walks.
Stated and proved
Lemma 1.5 on cycles in graphs and on decomposition into cycles of
graphs with all degrees even.
Notion of Eulerian circuits, an example.
Stated and proved Euler's theorem (Theorem 1.6) that
characterizes graphs with Eulerian circuits.
A refinement of Euler's Theorem to Eulerian trails (Corollary 1.7).
A discussion of n-vertex simple triangle-free graphs with many edges.
Stated Mantel's Theorem (Theorem 1.8)(Theorem 1.3.23 in the book).
- 5. Friday, 01/26:
Stated and proved Mantel's Theorem (Theorem 1.8)(Theorem 1.3.23 in the book) on the maximum
number of edges in
n-vertex simple triangle-free graphs and presented sharpness examples.
Degree sequences of graphs.
A characterization of degree sequences of graphs (Proposition 1.9)(1.3.28 in the book).
A definition of graphic sequences.
Stated, showed how to apply and proved the Havel-Hakimi Theorem
(Theorem 1.10)(1.3.31 in the book)
on graphic sequences.
- 6. Monday, 01/29:
Presented a proof of Problem 4 in HW1.
Repeated a part of proof of the Havel-Hakimi Theorem
(Theorem 1.10)(1.3.31 in the book)
on graphic sequences.
Directed graphs: Examples, tournaments.
Out-neighbors and in-neighbors,
degrees, outdegrees and indegrees of
vertices in digraphs. Degree sum formula for digraphs (Proposition 1.11).
Adjacency and incidence matrices; directed walks, trails,
paths and cycles. Examples.
Underlying undirected graphs.
Connected and weakly connected digraphs.
- 7. Wednesday, 01/31:
Proved Lemma 1.13 on digraphs in which for every vertex the in-degree equals to the out-degree.
Proved a characterization
of Eulerian directed graphs (Theorem 1.12) using Lemma 1.13.
De Bruijn graphs: definition and examples. Properties of de Bruijn graphs.
Special circular arrangements of
0's and 1's, and Eulerian circuits in the de Bruijn graphs. An example.
Kings in tournaments. An example.
Stated and proved Theorem 1.14 (Prop. 1.4.30 in the book)
on the existence
of kings.
- 8. Friday, 02/02:
Main results in Chapter 1.
Presented a proof of Problem 1 in HW2.
Definitions and examples of trees and forests.
Lemma 2.1 (2.1.3 in the book) on simple properties of trees.
Stated and
proved Theorem 2.2 (2.1.4 in the book):
a characterization theorem for trees.
- 9. Monday, 02/05:
Recalled Theorem 2.2 (2.1.4 in the book):
a characterization theorem for trees.
Distance in graphs:
eccentricity, diameter, radius. Examples.
Centers of graphs, examples.
Stated and proved
Theorem 2.3 (2.1.13 in the book): Jordan's theorem on centers of trees.
A couple of comments on labeled trees.
Prufer codes: definition and examples.
Stated and half-proved three properties of Prufer codes.
- 10. Wednesday, 02/07:
Restated and proved three properties of Prufer codes.
Stated and
proved Theorem 2.4 on Prufer codes.
Stated and proved Cayley Formula (Theorem 2.5)(Theorem 2.2.3 in the book).
Spanning trees in general
graphs. An example. Stated Matrix Tree Theorem (Theorem 2.6)(Theorem 2.2.12 in the book). An example of application of Matrix Tree Theorem (Theorem 2.6)(Theorem 2.2.12 in the book). Started Minimum Spanning Tree Problem.
- 11. Friday, 02/09:
A discussion of the
Minimum Spanning Tree Problem.
Stated Lemma 2.7 on minimum
spanning trees. Presented Prim's Algorithm and Kruskal's
Algorithm for finding minimum spanning trees in a graph.
Quiz 1.
- 12. Monday, 02/12:
A discussion of Quiz 1. Presented solutions of Problems 1 and 2 in HW3.
Proved Lemma 2.7 on minimum
spanning trees.
Maximum spanning trees. Main results in Chapter 2.
Matchings in graphs: basic definitions,
examples, perfect matchings. M-alternating and
M-augmenting paths.
Stated and proved Berge's Theorem (Theorem 3.1)(Theorem 3.1.10 in the book) on M-augmenting paths.
- 13. Wednesday, 02/14:
A digression on Sylvester.
Matchings in bipartite graphs.
Stated and proved Hall's Theorem (Theorem 3.2)(Theorem 3.1.11 in the book)
on matchings in bipartite graphs. Systems of distinct representatives.
Proved Marriage Theorem (Corollary 3.3)(Corollary 3.1.13 in the book)
on perfect matchings in bipartite regular
graphs.
- 14. Friday, 02/16:
Presented solution of Problem 3 in HW4.
The notion of vertex cover.
A relation between the independence number and the size of a minimum
vertex cover in a graph.
A relation between the size of a
maximum matching, and the size of a minimum
vertex cover in a graph.
Proved Konig-Egervary Theorem
on vertex cover in bipartite graphs (Theorem 3.4)(Theorem 3.1.16 in the book).
The notion of edge cover, examples.
- 15. Monday, 02/19:
A discussion of relations between edge covers and vertex covers.
Stated and proved Gallai's Theorem
on maximim matchings and edge covers in
graphs without isolated vertices (Theorem 3.5)(Theorem 3.1.22 in the book).
Introduced and discussed stable matchings.
The Gale-Shapley Algorithm and an example.
Started to prove that the Gale-Shapley Algorithm for finding
stable matching works correctly (Theorem 3.6)(Theorem 3.2.18 in the book).
- 16. Wednesday, 02/21:
Proved that the Gale-Shapley Algorithm for finding
stable matching works correctly (Theorem 3.6)(Theorem 3.2.18 in the book).
A short discussion of 3-partite stable
matchings. An example of absence of stable matching in the Roommate Problem.
Matchings in general graphs, examples.
An example of a 3-regular graph with no perfect matching.
Odd components and k-factors, an example.
Stated and started to prove
Tutte's Theorem on perfect matchings in graphs
(Theorem 3.7)(Theorem 3.3.3 in the book).
- 17. Friday, 02/23:
Proved
Tutte's Theorem on perfect matchings in graphs
(Theorem 3.7)(Theorem 3.3.3 in the book).
Proved Petersen's theorem (Theorem 3.8)(Corollary 3.3.8 in the book)
on
perfect matchings in 3-regular graphs with no cut edges.
A discussion of the first paper of Petersen on graph theory.
- 18. Monday, 02/26:
Presented a proof of Problem 5 in HW5.
Proved Petersen's Theorem on
2-factors in 2k-regular graphs (Theorem 3.9)
(Theorem 3.3.10 in the book).
Stated and proved the corollary
that each 2k-regular graph decomposes into k 2-factors.
Quiz 2.
- 19. Wednesday, 02/28:
A short discussion of Qui 2.
Stated and proved the
Berge-Tutte Formula (Theorem 3.10) (Corollary 3.3.7 in the book).
Proved Corollary 3.11 (Remark 3.3.5 in the book)
on graphs with
an even number of vertices that do not have a perfect matching.
The six important results in Chapter 3.
First definitions and examples for connectivity.
- 20. Wednesday, 02/28 at 7pm:
Exam 1 from 7pm to 8:30pm.
- 21. Friday, 03/01:
A short discussion of Test 1.
Proved Lemma 4.1 (restatement of the definition of connectivity).
Introduced edge connectivity, an example.
Gave a definition of a k-edge-connected graph.
Stated and proved Theorem 4.2 (Theorem 4.1.9 in the book) on relations between
connectivity, edge-connectivity and minimum degree of a graph.
Stated and proved that the edge-connectivity of a 3-regular graph
with at least 4 vertices
always equals
its connectivity (Theorem 4.3) (Theorem 4.1.11 in the book).
Stated and started to prove Whitney's Theorem on 2-connected graphs
(Theorem 4.4) (Theorem 4.2.2 in the book).
- 22. Monday, 03/04:
Briefly discussed the proof of Theorem 4.2.
Proved Whitney's Theorem on 2-connected graphs
(Theorem 4.4) (Theorem 4.2.2 in the book).
Stated and proved Expansion Lemma (Lemma 4.5)(Lemma 4.2.3
in the book). Stated and proved a
characterization theorem for 2-connected graphs (Theorem 4.6)
(Theorem 4.2.4 in the book).
Proved that subdivisions
of 2-connected graphs are 2-connected (Corollary 4.7).
Defined ears in graphs and ear decompositions.
- 23. Wednesday, 03/06:
Repeated the definitions of ears in graphs and ear decompositions.
Stated and proved
a characterization of 2-connected graphs in
terms of ear decompositions (Theorem 4.8) (Theorem 4.2.8 in the book).
Notions of x,y-cuts and related characterstics. Examples.
Stated and started to prove
Menger's Theorem for vertex connectivity (Theorem 4.9) (Theorem 4.2.17 in the book).
- 24. Friday, 03/08:
Presented a solution to Problem 2 in HW6.
Proved
Menger's Theorem for vertex connectivity (Theorem 4.9) (Theorem 4.2.17 in the book). Stated and proved Lemma 4.10 (Lemma 4.2.20 in the book) on edge deletion in k-connected graphs.
- 25. Monday, 03/18:
Stated and proved Theorem 4.11 on internally disjoint paths in k-connected graphs.
Stated Theorem 4.12 - the edge version of Menger's Theorem (Theorem 4.2.19 in the book).
Stated Theorem 4.13 (an analog of Theorem 4.9
and Theorem 4.14 (an analog of Theorem 4.10)
for directed graphs.
Proved Fan Lemma (Theorem 4.2.23 in the book).
A bonus problem. Started flows in networks: definitions and first properties.
- 26. Wednesday, 03/20:
Showed a solution to the bonus problem.
Continued flows in networks: definitions and simple properties.
Proved that each
circulation in a network with m edges is the sum of at most m-1 flows along cycles
(Lemma 4.15). Stated and proved Theorem 4.16 that each
flow in a network with m edges is the sum of at most m flows along cycles,
s,t-paths and t,s-paths.
- 27. Monday, 03/25:
Presented solutions of Problems 1,3 and 5 of HW7. A numberical example
for partitioning a flow into simple flows. Quiz 3.
- 28. Wednesday, 03/27:
Comments on Quiz 3.
Introduced s,t-cuts and their capacities.
Proved Claim 4.17: an inequality
between the minimum capacity of an s,t-cut in a network and the maximum value of
a feasible flow in this network.
Stated the MaxFlow-MinCut Theorem (Theorem 4.18).
A residue network for a flow in a network.
Run an example of Ford-Fulkerson's algorithm for finding maximum flow in a network
and pointed out how it works in general.
- 29. Wednesday, 03/27 at 7pm:
Exam 2 from 7pm to 8:30pm.
- 30. Monday, 04/01:
A discussion of Test 2.
Proved the MaxFlow-MinCut Theorem (Theorem 4.18). Pointed out how to find an
s,t-cut of
minimum capacity when the residue network has no s,t-paths.
A discussion
of efficiency of the Ford-Fulkerson's algorithm.
An observation on integral-valued
flows in networks with integral capacities.
Integral flows. Proved the edge version
of Menger's
Theorem for directed graphs using MaxFlow-MinCut Theorem (Theorem 4.13).
A comment on algorithms.
- 31. Wednesday, 04/03:
A short discussion of Test 2.
Pointed out how to derive the vertex version
of Menger's
Theorem for directed graphs using MaxFlow-MinCut Theorem (Theorem 4.12) from the edge version (Theorem 4.13).
Proved that finding maximum matchings in
a bipartite graph is a Max Flow Problem (Theorem 4.19).
Main results in Chapter 4. Definitions and examples of planar and plane graphs.
Faces and their degrees.
- 32. Friday, 04/05:
Faces and their degrees.
Proved the degree-sum formula for faces of plane graphs (Theorem 6.1).
Defined dual graphs.
Stated and proved Euler's Formula (Theorem 6.2).
Almost proved Corollary 6.3 that for n>2 every n-vertex simple planar graph
has at most 3n-6 edges; each such triangle-free graph has at most
2n-4 edges.
Proved Corollary 6.4:
K_5 and K_{3,3} are non-planar.
- 33. Monday, 04/08:
Finished the proof of Corollary 6.3 that for n>2 every n-vertex simple planar graph has at most 3n-6 edges; each such triangle-free graph has at most
2n-4 edges.
Subdivisions of graphs, stated
Kuratowski's Theorem (Theorem 6.5).
A subdivision
of K_{3,3} in Petersen Graph. Edge contractions and their properties.
Discussed a challenge on nonplanar subgraphs of Petersen Graph.
Wagner's criterion of planarity of graphs
(Theorem 6.6). Using contractions to prove that Petersen's graph is
not planar.
Outerplane and outerplanar graphs:
definitions and examples. Proved the characterization of outerplanar graphs,
Theorem 6.7. Maximal planar graphs and
triangulations.
- 34. Wednesday, 04/10:
Proved Theorem 6.8 on maximal planar graphs and
triangulations. Main results in Chapter 6.
Graph colorings: definitions and examples.
4-Color Theorem.
Simple properties of chromatic number (Proposition 5.1).
Greedy coloring.
Maximum degree plus one colors are enough to color a graph
(Proposition 5.2).
An example of a tree and an ordering such that greedy coloring
needs 4 colors for coloring of this tree.
Two definitions of d-degenerate graphs.
Every d-degenerate graph is (d+1)-colorable (Proposition 5.4).
Every planar graph is 6-colorable (Theorem 5.5).
- 35. Friday, 04/12:
Presented a proof of Problem 1 in HW8.
Two definitions of d-degenerate graphs. Proved equivalence of the
definitions (Proposition 5.3).
Every d-degenerate graph is (d+1)-colorable (Proposition 5.4).
Every planar graph is 6-colorable (Theorem 5.5).
Notion and examples of color-critical graphs.
- 36. Monday, 04/15:
A discussion of color-critical graphs. Stated and proved Theorem 5.6 on
properties of k-critical graphs.
Quiz 4.
- 37. Wednesday, 04/17:
A short discussion of Quiz 4.
Mycielski's Construction of triangle-free graphs
with high chromatic number (Theorem 5.7): description and properties.
Stated
and started to prove Brooks' Theorem (Theorem 5.8) (Theorem 5.1.22 in the book).
- 38. Wednesday, 04/17 at 7pm:
Exam 3 from 7pm to 8:30pm.
- 39. Friday, 04/19:
A discussion of Test 3.
Proved Brooks' Theorem (Theorem 5.8) (Theorem 5.1.22 in the book).
An improvement for maximum degree 7 (Theorem 5.9).
Edge coloring: first definitions and examples.
Edge coloring of cycles.
- 40. Monday, 04/22:
Edge coloring of complete graphs.
Every bipartite graph with maximum degree D is edge-D-colorable.
A 3-regular graph with a cut edge is not edge-3-colorable.
Petersen's graph is not edge-3-colorable.
An application by Shannon.
Example of Shannon Triangle - a graph with maximum degree D and
edge chromatic number 3D/2. Line graphs and their vertex coloring.
Stated Shannon's Theorem (Theorem 7.1) on edge coloring.
Stated and commented Vizing's Theorem (Theorem 7.2) on edge coloring of simple
graphs.
Stated and commented
Tait's Theorem on edge coloring of 3-regular 2-connected plane graphs
(Theorem 7.3).
- 41. Wednesday, 04/24:
Reminded a statement of the Four Color Theorem in the language of edges colorings.
Hamiltonian cycles: definitions and examples. Hamilton's puzzle.
Stated and proved Dirac's Theorem (Theorem 7.5)
on hamiltonian cycles in n-vertex graphs with
minimum degree at least n/2. Two extremal examples.
Petersen's graph is not hamiltonian.
Proved Tutte's example of a 3-regular 3-connected plane graph that does not have a hamiltonian cycle (see in the book).
- 42. Friday, 04/26:
Complete multipartite graphs. Turan graph T(n,k).
Stated Turan's Theorem (Theorem 5.10) (Theorem 5.2.9 in the book) on the maximum number of edges in n-vertex simple
graphs not containing K_{k+1}.
Stated and proved Ershov-Kozhukhin Theorem (Theorem 5.11) (Exercise 5.2.6 in the book)
on the minimum number of edges in a k-chromatic n-vertex
connected graph.
Make-up Quiz.
- 43. Wednesday, 05/01:
Presented a proof of a problem in HW9.
Review of the course,
topics for the final. Ten most important theorems on graphs.
A proof of the 5-Color Theorem.
Last changed on May 1, 2024.