Home Page for Math 3V03: Graph Theory, Winter 2011-2012

Textbooks
  • (Main) Introduction to Graph Theory, 2nd edition, Douglas B. West, Prentice Hall
  • Graph Theory with Applications, J.A. Bondy & U.S.R. Murty, North-Holland, 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, k-connectivity
  • 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 self-complementary 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)

Week Monday Wednesday Thursday Problems
0. Jan 2 - 6 - Introduction 1.1
1. Jan 9 - 13 1.1 1.1 1.1 Homework 1   (solutions)     Recommended problems 1   (solutions)
2. Jan 16 - 20 1.1 1.2 1.2     HW 1 Due Homework 2   (solutions)     Recommended problems 2   (solutions)
3. Jan 23 - 27 1.2 1.2 1.3     HW 2 Due Homework 3   (solutions)     Recommended problems 3   (solutions)
4. Jan 30 - Feb 3 1.3 1.3 1.3     HW 3 Due
5. Feb 6 - 10 review 1.4 Midterm I (solutions) Homework 4   (solutions)     Recommended problems 4   (solutions)
6. Feb 13 - 17 2.1 2.1 2.1     HW 4 Due Homework 5   (solutions)     Recommended problems 5   (solutions)
7. Feb 20 - 24 recess recess recess
8. Feb 27 - Mar 2 2.2 2.2 2.3     HW 5 Due Homework 6   (solutions)     Recommended problems 6   (solutions)
9. Mar 5 - 9 2.3 3.1 3.1     HW 6 Due
10. Mar 12 - 16 3.1 3.1 Midterm II (solutions) Homework 7   (solutions)     Recommended problems 7   (solutions)
11. Mar 19 - 23 4.1 4.1 4.2     HW 7 Due Homework 8   (solutions)     Recommended problems 8   (solutions)
12. Mar 26 - 30 4.2 5.1 5.1     HW 8 Due Homework 9   (solutions)     Bonus problem
13. Apr 2 - 6 5.1 ?     HW 9 Due (optional) -

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 4-vertex graphs. Self-complementary graph. Graph decomposition. Walks, trails, paths, closed walks. Lemma: Every u,v-walk contains a u,v-path. Connected vertices, connected graphs, components. Cut-edge, cut-vertex. Theorem: An edge is a cut-edge 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 non-extendible 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. k-regular graph. Degree-Sum formula and its corollaries. The k-dimensional cube.
  • Week 4. Example: Petersen graph has 10 6-cycles. 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. H-free graph. Mantel's theorem on the maximum number of edges in an n-vertex triangle-free 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)|=n-1 (iii) G is acyclic and |E(G)| = n-1 (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 self-study 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, M-alternating and M-augmenting paths. Thm: M is a maximum matching iff there is no M-augmenting path. Hall's Theorem: An X,Y-bigraph 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. Konig-Egervary 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, k-connected graph, connectivity. Disconnecting set of edges, edge cut, k-edge-connected graph, edge-connectivity. Vertex connectivity is less than or equal to edge-connectivity (equality for 3-regular graphs), which is less than or equal to the minimum degree. Counting number of edges in an edge-cut. Block, proposition: two blocks share at most one vertex. Internally disjoint paths. Thm: A graph with at least 3 vertices is 2-connected 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, k-colorable graph, chromatic number \chi(G), k-critical graph. Observation: k-colorable=k-partite. Lower bounds for chromatic number. Greedy coloring, upper bounds. Micielski construction of triangle-free graphs with arbitrarily large chromatic number (*).
  • Week 13. (*) Planar graphs and chromatic number.

Picture by Ahsan