## 189-480B/189-695B, A reading course in Combinatorics and Graph Theory

### Lectures

### Student Talks

### Instructor

### Texts (Recommended)

### Outline

### Grading

### Topics for the talks

### Problem sets

**Problem set 1** (due Thursday, Jan. 18), covering Ch. 8,
sections 8.1 - 8.5 of Biggs' book. **Turn in:** Biggs, Ch. 8
(pp. 177-178), #4, 7, 14, 18, 19.
Additional problem: Let A be the adjacency matrix of a connected graph G that
has diameter d. Prove that the degree of the minimal polynomial of A is
at least d. **Practice problems** (don't turn them in):
Biggs, p. 162 (section 8.2), #1,2; p. 165 (section 8.4), #2,5;
p. 171, #1; p. 177, #3, 5, 6, 12

**Problem set 2** (due Tuesday, Jan. 30), covering Diestel
(section 1.9) and the matrix tree (Kirchhoff's) theorem. **Problems to
turn in:**
postscript, pdf.
**Practice problems** (don't turn in). For a
$k$-regular graph $G$, prove that $k$ is an eigenvalue whose multiplicity
is equal to the number of connected components of $G$
Find the eigenvalues and tree numbers of the $n$-cube, the Petersen
graph, and the complete graph K_{a,b}

**Problem set 3** (due Thursday, March. 1), covering Diestel,
(sections 3.3, 6.1, 6.2) and Biggs (sections 11.1-11.4). **Problems
to turn in:**
Prove that in a two-connected graph with at least three vertices, any two
vertices can be joined by two internally disjoint paths (DO NOT use any
results about flows in networks).
Biggs, Ch. 11, p. 246, # 3, 6, 12. ** Ignore problem 15 on p. 247; it is
wrong as stated.** Additional problem:
postscript, pdf.
**Practice problems** (don't turn in). Biggs, Ch. 11, p. 230
(section 11.1), #2,4; p. 233 (section 11.2), #1; p. 237 (section 11.3), #1;
p. 240 (section 11.4), #1,2.

**Problem set 4** (due Thursday, March 8), covering
Biggs (sections 8.6, 8.7; sections 10.1-10.5) and Diestel (chapters 2 and 4).
**Problems to turn in:** Biggs, Ch. 8, p. 179, #22. Ch. 10, p. 225,
#1,5,7,10,17. **Practice problems** (don't turn in). Biggs, Ch.
10 p. 209 (section 10.2) #2; p. 211 (section 10.3) #4,5,6; p. 219 (section
10.4) #2,3; p. 223 (section 10.5) #2,3. A funny "practice" problem:
assume that you know that any FINITE map in the plane is 4-colourable;
prove the same statement for a (countably) INFINITE map.

**Problem set 5** (due Tuesday, March 20), covering Biggs,
sections 4.4-4.7, 6.4-6.5, 10.3, 16.5-16.8. **Turn in SIX** of
the following problems:
Biggs, Ch. 4, p. 87, #8,10; Ch. 6, p. 130, #15,20; Ch. 10, p. 226, #10;
Ch. 16, p. 372, #5,10,12.
**Practice problems** (don't turn in). Biggs, p. 74, #2,4,5; p. 78
#2,3; p. 79 #5 (there is a typo in the formula for phi(n)); p. 83, #2,3,4;
p. 86 #2,4; p. 87 #4,13,16,18,19; p. 125 #3,4; p. 128 #2,4;
p. 130 #11,13,17; p. 215 #2,3; p. 226 # 11,20; p. 354 #1,2,4; p. 357 #2,3;
p. 360 #2,3,4; p. 364 #2,4,5; p. 367 #1,3,4; p. 372 #7,8,11,14,17.

**Problem set 6** (due Thursday, March 29), covering Biggs,
sections 5.1-5.5, Chapters 18, 19. Also, review Chapter 14.
**Turn in SIX** of the following problems: Biggs, Ch. 5,
p. 111, #10,12,19; Ch. 14, p. 319, #7,[20 and 21]; Ch. 18, p. 421,
#10,13,17,20; Ch. 19, p. 439, #4,8,11,16. **Practice problems** will
be added later.

Everybody is excused from **two** of the problem sets 4,5,6 (so that
you have time to prepare for your talk). You can choose which problem
sets you would like to skip; I'll adjust the grading so that every problem
set has the same maximal score.

### How to get started

Things to review (we shall review some of them later, but it's a good
idea to start early): Groups - permutations, subgroups, cosets,
Lagrange's theorem, cyclic groups; Rings - polynomials, Euclidean algorithm
for polynomials and integers, greatest common divisor,
prime factorization, fields **Z**/p**Z**; Linear Algebra - matrices,
determinants, eigenvalues and eigenvectors, Cauchy-Binet theorem.
If you haven't seen graphs before, you can look at a nice online
graph glossary, work through a few tutorials,
and do some
exercises at
Mathmania. This site also has a nice introduction to
knots
and other things.
A previous site is very similar to the
Mega-Math page at Los Alamos.
A nice online course
in graph theory.
Online graph theory glossaries:
1,
2
Other nice online introductions to graph theory problems:
The bridges of
Königsberg;
spanning trees;
Three
Houses, Three Utilities;
Travelling
Salesman
### Web Links

13h15 SÉMINAIRE/SEMINAR (Combinatoire et informatique
mathématique):
UQAM, Pav. Président-Kennedy, 201, av. Président-Kennedy,
salle PK-4323
Conférencier: Christophe Reutenauer, Université de Strasbourg
et LaCIM-UQAM. **Titre:** Sur l'inverse d'un mot.
There will be a special lecture by Dr. Vera Rosta on
"Generalized and Geometric Ramsey numbers" on Monday, February 5, from
15:30-16:30 in Burnside 920. The abstract is on the bulletin board on the
10th floor.
A year on
Groups and Geometry at CRM
McGill, Dept. of Mathematics
and Statistics
McGill, Dept. of Computer Science
LaCIM
CRM:L'Officiel
Univ. of Waterloo, Dept. of Combinatorics and Optimization
DIMACS
Centre for Discrete and Applicable
Math, London School of Economics
Electronic Journal of
Combinatorics, World Combinatorics Exchange
SIAM activity group
on Discrete Mathematics
Combinatorics:
UC Davis front end for Loas Alamos e-print archive
Combinatorics Net
Graph Theorists: White pages and another
list
Google directories in
Combinatorics and Graph Theory
Math Archives: Combinatorics
Erdös
Number page
The Four Colour Theorem (proved in 1976 by Appel and Haken):
history, and a
new proof
(by Robertson, Sanders, Seymour and Thomas).
Combinatorial Catalogues
Databases for Moore graphs, cages etc:
M. Meringer,
G. Royle,
WCE page
The Hamiltonian page
The Steiner Tree page
Open problems: a
list at DIMACS;
Topological Graph Theory;
Graph Coloring;
an enlarged list of Bondy and Murty
(by C. Locke);
The Geometry Junkyard; Perfect
Graphs;
MathSoft list
(general math).
Brendan McKay
"Can you hear the shape of the drum?" pages:
short history,
and a
paper by Buser, Conway, Doyle and Semmler
Web applications (search engines): a paper by
S. Brin and L. Page (founders of
Google), and a later
paper on web page reputations by D. Rafiei and
A. Mendelzon.