COMP 61: Discrete Math
This page will contain all notes and links for the lectures on graphs.
Week 12, Tuesday, April 1
- Covered: Intro to graphs. Isomorphism. Spanning subgraphs and induced subgraphs.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 9, section 47 and the first 2 pages of section 48.
- Links
- Graph isomorphism
- Graph enumeration
- Miscellaneous
Week 13, Tuesday, April 8
- Covered: Cliques, independent sets, Ramsey numbers.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 9, section 48.
- Links
- Ramsey numbers (cliques vs independent sets)
- R(x,y) represents the smallest integer N such that in any graph of size at least N there is
either a clique of size x or an independent set of size y.
- Here is a
wiki about R(3,3).
- R(4,3)
Update: here is a link
showing R(4,3)=9, without resorting to a recurrence as in the previous link. (see 2 paragraphs before the 2nd figure).
- R(4,4): requires knowledge of R(4,3).
- R(5,5) is unknown!
- wiki on Ramsey's theorem.
Notice that there are also Ramsey numbers with
more than 2 parameters.
- Games
- "Sim" (wiki) is a game where 2 players take turns
coloring the edges of K6. One player uses red and the other uses blue. Whoever completes a
triangle of their own color loses. An extended version of the game asks two players to color
K18, while avoiding coloring a monochromatic K4. There is a 3-player
version as well. Ramsey theory tells us that these games cannot end in a draw.
- A variant of sim is Hajnal's triangle-free game, discussed
here.
Two players take turns adding edges, with the restriction that neither can complete a triangle. However, there are no
colors in this game. A player wins if the other player cannot add an edge.
The game can also be played using a score that
is just the total number of edges added. The goal of one player is to maximize the score, and the goal of the 2nd
player is to force a configuration where no edge can be added, as quickly as possible. Finally there is also a variant
with an additional constraint, where the graph must remain connected at all times.
- Existential, or non-constructive proofs (following a question asked in class).
- Here is a cute example of an existential proof, even though constructive ones exist as well. The question is:
Are there any two irrational numbers a and b, such that ab is rational?
The answer is, yes. One particular solution combines powers of square roots of 2's in two different ways, so that one of the two options gives the desired a and b. The conclusion is that a and b do exist, but we don't know what they are (although there are two options for the pair). It turns out that there is a method of determining which is the ``true" pair, but in the absence of any more mathematical arguments, the proof remains existential.
I do hope to expand this section one day, with more such proofs, in a way that is accessible to comp61.
Week 14, Tuesday, April 15
- Covering: connectivity and trees.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 9, sections 49, 50.
- No links. If you find a particularly useful or interesting link, please let me know.
Week 15, Tuesday, April 22
- Covering: Planarity. Intro to vertex coloring.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 9, sections 52, part of 53.
- Links
- Planarity
- Euler's formula (for planar graphs)
- The wiki on planar graphs contains a
section on Euler's formula.
- 20 proofs of Euler's formula
- The formula V-E+F=2 is just a particular case of a far greater body of work. As mentioned in class,
if you were to draw a connected graph on a sphere, you'd get the same relation;
The Euler characteristic would be 2.
Similarly, count the vertices, edges and faces on any convex
polyhedron. Other surfaces
have
other characteristic numbers.
- The role of K5 and K3,3
- The wiki on planar graphs starts out by mentioning the theorems of Kuratowski and Wagner,
which essentially say that a graph G is non-planar if and only if the shape of a
K5 or of a K3,3 is present in G.
See here.
Look at the two figures, showing two (non-planar) graphs not directly containing a
K5 or a K3,3, but that implicitly contain those shapes.
The section that follows in the wiki discusses other planarity criteria. Theorem 1 in particular is quite simple, and easy to prove.
- (advanced) notes on Kuratowski's theorem.
The advanced part is proving that any graph not containing K5 or K3,3 as a subgraph -- or as a minor -- must be planar. In other words, non-planarity implies finding such a subgraph/minor.
In our class we only discuss the other direction: i.e., that containing one of those subgraphs implies non-planarity.
Week 15, Thursday, April 24 (please see the graphs page as well, for this day).
- Covered: More vertex coloring.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 9, section 53.
- Links
- Vertex coloring
- Hadwiger-Nelson problem
- This is an awesome vetex coloring problem, with an infinite number of vertices: all points in the plane.
It is explained nicely in this
wiki.
A few things that we would have talked about, if time permitted:
(If you stay in CS, you'll surely see these at some point. Look these up, to at least knowing what they mean)
- Eulerian paths (covered in chapter 9, section 51).
- Hamiltonian paths.
- Spanning trees. These are covered quite thoroughly in comp160.
- Binary trees. Also covered in comp160.
- Edge coloring
- The idea here is to color edges of a graph, so that no vertex is incident to 2 edges of the same color.
Of course, you must minimize the number of colors used.
- wiki
(see the applications section).