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

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
*K*. 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_{6}*K*, while avoiding coloring a monochromatic_{18}*K*. There is a 3-player version as well. Ramsey theory tells us that these games cannot end in a draw._{4} - 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.

- "Sim" (wiki) is a game where 2 players take turns
coloring the edges of

- 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 a^{b}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.

- Here is a cute example of an existential proof, even though constructive ones exist as well. The question is:

- Ramsey numbers (cliques vs independent sets)

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 K
_{5}and K_{3,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 K_{5}or of a K_{3,3}is present in G. See here. Look at the two figures, showing two (non-planar) graphs not directly containing a K_{5}or a K_{3,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 K
_{5}or K_{3,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.

- 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

- Euler's formula (for planar graphs)

- 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).