Home Page for Math 3V03: Graph Theory, Winter 20112012
Textbooks
 (Main) Introduction to Graph Theory, 2nd edition, Douglas B. West, Prentice Hall
 Graph Theory with Applications, J.A. Bondy & U.S.R. Murty, NorthHolland,
available online
Course objectives:
To understand the fundamental properties of graphs and their applications. Topics include:
 Fundamental concepts, matrix representation, connected graphs, vertex degrees and graphic sequences
 Trees and distance, enumeration, Kruskal's algorithm, Dijkstra's algorithm
 Matching in bipartite graphs
 Connectivity and cuts, kconnectivity
 Coloring
Instructor: Libor Barto, HH 409, ext 27031
Course meeting time: Mo We Th 13:30  14:20 in HH 102
Email: lbarto at math dot mcamster dot ca
Office hours: Mo We Th 14:30  15:30 in HH 409
Course outline with detailed information about how the course will be marked, procedures for dealing with absences, university regulations.
Briefly:
 Marking scheme: homework 35%, midterm I 15%, midterm II 15%, final 35%
 Homeworks are posted here a week before due date (or earlier), the two lowest scores will be dropped
 Recommended problems are posted here as well
Announcements
 The file with marks is updated and it now includes the last assignment and the total mark for homework. I decided to count 6 best assignments (out of 9).
 Unfortunately I have to cancel Monday's office hours . On Tuesday I will be available from 11:00.
 I have marked (*) those topics which will not appear in the midterm
 I will be in my office on Thursday,
Monday , Tuesday from 13:00 to 15:30 and on Wednesday from 10:30.
 Final exam is on Wednesday, April 11 in IWC 1 (1) at 14:00. It covers all the material from class. There are some "no justification needed" problems, standard problems (similar to midterms),
a statement and proof of one of the four selected theorems (characterization of bipartite graphs, characterization of Eulerian graphs, characterizations of trees, Hall's Theorem), and
one of the recommended problems. Good luck!
 A picture from today's class taken by Ahsan is below the summary.
 The file with marks is updated and it now includes the second midterm. Please check your grades and let me know about discrepancies. Solutions will appear soon
(most likely on Monday).
 The second midterm is on Mar 15 in BSB/137 . It will cover the material from weeks 6,8,9 + Monday Mar 12
(that is, trees, distances, Prufer code and counting, Kruskal's and Dijkstra's algorithms, matching). Don't forget to bring your student ID. Good luck!
 Below you can find marks for Midterm 1 and assignments, it's sorted by the last four digits of your student ID. I'll keep the file updated.
Solutions to Midterm 1 are in the table.
 The 4th round of problems is here. Hurray!
 The first midterm is on Feb 9 in T29/101. It will cover the material we discussed in class, which roughly corresponds to sections 1.1.,1.2 and 1.3 from the textbook.
 The office hours on Wednesday Feb 8 are canceled.
 Recommended problem 3.2 is inclomplete. The second sentence should be "Prove that G is a biclique ( = a complete bipartite graph)".
 Solutions to the first problem sets and the second problem sets are posted.

Below the course calendar you can find a short summary of what we have learned so far.
 The first set of homework problems and recommended problems is here (see the table below), it is due January 19 before the class.
We have not discussed some notions appearing there (we will do it on Monday). For those who cannot wait and do not have the textbook:
Definition. A graph is selfcomplementary if it is isomorphic to its complement.
Definition. A decomposition of a graph G is a list of its subgraphs such that every edge in G is an edge
of exactly one of the subgraphs in the list.
 The first class will be held on Wednesday, January 4 in HH 102 at 13:30.
Marks
Course calendar (tentative)
Summary
(*) not required

Week 1. Graph, loop, simple graph. Clique, independent set. Complement.
Theorem on friends and stragers: Every party of 6 people contains three mutual acquaintances or three mutual strangers.
Bipartite graph. Path, cycle, connected graph. Subgraph. Girth. The Petersen graph. Vertex degree. Adjacency matrix. Isomorphism, isomorphism class of graphs ("unlabeled graph"), P_n, C_n, K_n, K_{r,s}.

Week 2. Number of graphs with a given set of vertices, isomorphism classes of 4vertex graphs.
Selfcomplementary graph. Graph decomposition. Walks, trails, paths, closed walks. Lemma: Every u,vwalk contains a u,vpath. Connected vertices, connected graphs, components.
Cutedge, cutvertex. Theorem: An edge is a cutedge iff it belongs to no cycle. Lemma: Every closed odd walk contains an odd cycle. Theorem: A graph is bipartite iff it has no odd cycle.

Week 3. Eulerian circuit, Eulerian trail. Theorem: A graph has an Eulerian circuit iff it is even
and it has at most one nontrivial component. Proof using Lemma: If every vertex has degree at least 2, then the graph contains a cycle.
Another proof using Lemma: Every nonextendible trail in an even graph is closed.
Theorem: Connected nontrivial graph with exactly 2k odd vertices decomposes into max{k,1} trails (and this is an optimal number).
Induced subgraph. kregular graph.
DegreeSum formula and its corollaries. The kdimensional cube.

Week 4. Example: Petersen graph has 10 6cycles. Disjoint union (=sum) of graphs. The maximal value of \delta(G) among disconnected simple graphs with n vertices.
Theorem: Every loopless graph G has a bipartite subgraph with at least e(G)/2 edges. Hfree graph. Mantel's theorem on the maximum number of edges in an nvertex trianglefree graph.
Degree sequence, graphic sequence, theorem: a sequence is graphic iff the sequence, obtained by deleting its largest element D and substracting D from its D next largest elements, is graphic.

Week 5. (*) Directed graph (=digraph), outdegree, indegree. Theorem: A digraph has an Eulerian circuit iff d+(v)=d(v) for all v and the underlying graph has at most one nontrivial
component. De Bruijn graph, De Bruijn cycles.

Week 6. Forest (=acyclic graph), tree, leaf. Lemma: A nontrivial tree has at least 2 leaves. Lemma: Deleting a leaf from a tree produces a tree.
Theorem: If n=v(G) then TFAE (i) G is a tree (ii) G is connected and E(G)=n1 (iii) G is acyclic and E(G) = n1 (iv) G has no loops and a unique
path between any two vertices. Spanning subraph, spanning tree. Distance, eccentricity, diameter, radius, center, Wiener index. Thm: The center of a tree is a vertex or
an edge.

Week 7. Intesive selfstudy of graph theory.

Week 8. Prufer code of a tree, Cayley's Formula for the number of trees on a given vertex set, number of trees with given vertex degrees.
Kurskal's Algorithm for finding a minimum spanning tree in a weighted graph.

Week 9. Dijkstra's Algorithm for finding distances in weighted graphs. Breadth First Search (*). Matching, perfect matching, saturated set, unsaturated set.
Maximal and maximum matchings, Malternating and Maugmenting paths. Thm: M is a maximum matching iff there is no Maugmenting path.
Hall's Theorem: An X,Ybigraph G has matching which saturates X iff G satisfies Hall's condition (i.e. fo every subset S of X, N(S) is geater than or equal to S).

Week 10. Vertex cover. KonigEgervary Theorem: In a bipartite graph, the maximum size of a matching = the minimum size of a vertex cover. Applications  Marriage Theorem (*),
Chinese Postman Problem (*).

Week 11. Vertex cut, kconnected graph, connectivity. Disconnecting set of edges, edge cut, kedgeconnected graph, edgeconnectivity. Vertex connectivity is
less than or equal to edgeconnectivity (equality for 3regular graphs), which is less than or equal to the minimum degree. Counting number of edges in an edgecut.
Block, proposition: two blocks share at most one vertex. Internally disjoint paths. Thm: A graph with at least 3 vertices is 2connected iff there are two
internally disjoint path between any two distinct vertices.

Week 12. \kappa(u,v), \kappa'(u,v), \lambda(u,v), \lambda'(u,v). Menger's theorem: \kappa'(u,v)=\lambda'(u,v) and \kappa(u,v)=\lambda(u,v) (if u,v are not adjacent), applications.
Vertex coloring, kcolorable graph, chromatic number \chi(G), kcritical graph. Observation: kcolorable=kpartite.
Lower bounds for chromatic number. Greedy coloring, upper bounds. Micielski construction of trianglefree graphs with arbitrarily large chromatic number (*).

Week 13. (*) Planar graphs and chromatic number.
Picture by Ahsan
