Graph Theory I

General Course Information

  1. Syllabus–Semester II 1998-99
  2. Generic Course Objectives
  3. Classroom Behaviour

Topics

  1. Introduction.
    1. Historical remarks (Königsberg, four-color problem, utility problem).
    2. Brief examples of graphs in mathematics, computer science, and the natural and social sciences.
  2. Combinatorial and relational preliminaries.
    1. Binary relations; equivalence relations and equivalence classes; partial orders
    2. Digraph of a relation. Digraph of a function f:A\to A
    3. Digraph of a permutation
  3. Basics.
    1. Graphs, digraphs, and multigraphs. Degrees, in- and out-degrees, and the handshaking lemmas.
    2. Isomorphism.
    3. Adjacency and incidence matrices; number of walks as entries of matrix powers.
    4. Walks, trails, paths, cycles, and components (components as classes of the walk-equivalence).
    5. Special graphs: complete graphs, complete bipartite graphs, paths, cycles, and trees. Elementary operations used later: deletion, contraction, and complement.
    6. Subgraphs, spanning subgraphs, and induced subgraphs. Number of labeled simple graphs on a fixed n-set: 2^{\binom{n}{2}}.
  4. Degree sequences.
    1. Graphic sequences.
    2. Havel–Hakimi algorithm and proof.
  5. Trees and spanning trees.
    1. Acyclic graphs and forests.
    2. Equivalent characterizations of trees: connected and acyclic; unique path between any two vertices; minimally connected; maximally acyclic; connected with n-1 edges.
    3. Leaves: every tree on n\ge 2 vertices has at least two leaves. Rooted trees. Spanning trees and their existence in a connected graph.
    4. Minimum spanning trees: cut property, Kruskal’s algorithm, Prim’s algorithm.
    5. Enumeration: deletion–contraction recurrence; Prüfer code for spanning trees of K_n; Cayley’s formula n^{n-2}. Optional: statement of the matrix-tree theorem.
  6. Connectivity.
    1. Distance, diameter, and radius.
    2. Cut-vertices, bridges, and 2-connected graphs.
    3. Blocks (maximal 2-connected subgraphs) and the block-cut tree; the analogous edge-blocks (maximal 2-edge-connected subgraphs) and their tree structure.
    4. Ear decomposition: every 2-connected graph is an ear assembly beginning with a cycle; use in inductive proofs.
    5. Vertex- and edge-connectivity; the inequalities \kappa\le\kappa'\le\delta.
    6. Menger’s theorem (vertex and edge versions), including the two-disjoint-paths characterizations of vertex- and edge-2-connected graphs.
  7. Eulerian and Hamiltonian graphs.
    1. Euler’s theorem: a connected graph has an Euler circuit if and only if every degree is even, and an Euler trail if and only if exactly zero or two degrees are odd.
    2. Hierholzer’s algorithm. Chinese Postman Problem (statement).
    3. Hamiltonian paths and cycles; necessary conditions (in particular, a Hamiltonian graph has no cut-vertex).
    4. Dirac’s theorem and Ore’s theorem. Remark: Eulerian circuits are polynomial-time; Hamiltonian cycle is NP-complete (statement only).
  8. Bipartite graphs and matchings.
    1. Characterizations: 2-colorable if and only if there is no odd cycle. BFS 2-coloring algorithm and extraction of an odd cycle when the graph is not bipartite.
    2. Matchings, maximum and perfect matchings, vertex covers.
    3. Alternating and augmenting paths; Berge’s lemma. Hall’s marriage theorem and the deficiency form.
    4. König’s theorem.
    5. Augmenting-path algorithm for bipartite matching.
    6. Statement of Tutte’s theorem.
  9. Planarity.
    1. Plane and planar graphs, faces.
    2. Euler’s formula n-m+f=2 for connected plane graphs.
    3. Consequences: m\le 3n-6 for simple planar graphs on n\ge 3 vertices, and m\le 2n-4 for simple bipartite planar graphs. Non-planarity of K_5 and K_{3,3}. Kuratowski’s theorem and Wagner’s theorem (statements; subdivisions and minors illustrated). Geometric duals of plane graphs. Optional: five-color theorem for planar graphs (sketch).
  10. Vertex and edge coloring.
    1. Proper vertex colorings and the chromatic number.
    2. Greedy bound \chi\le\Delta+1.
    3. Brooks’ theorem.
    4. Clique number and the inequality \omega\le\chi. Chromatic polynomial via the deletion–contraction recurrence; values on trees and complete graphs.
    5. Four-color theorem (statement).
    6. Edge coloring and the chromatic index; Vizing’s theorem (statement: \chi'\in\{\Delta,\Delta+1\}).

Notes

  1. The digraph of a pre-order order relation.
  2. The directed graph of a function f:A –> B where A is finite and B is a subset of A.
  3. Simple graphs.
  4. Some special graphs.
  5. Edge unlabelled graphs.
  6. Edge labelled graphs.
  7. Trees
  8. The last departure graph of an Euler tour.
  9. Bondy–Chvátal Closure and Hamiltonicity

Exercises

Text

  • J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.

Bibliography

  1. D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
  2. M. Behzad, G. Chartrand, and Linda Lesniak-Forest, Graphs and Digraphs, Wadsworth International Group, 1981.