Introduction to graph theory

From Wikiversity
Jump to navigation Jump to search

Introduction to Graph Theory[edit | edit source]

An introductory course from the School of Mathematics

This course aims to provide a thorough introduction to the subject of graph theory.

Course requirements[edit | edit source]

The following knowledge is required or desirable on commencement of study of this course:

Course outline[edit | edit source]

This is an approximate depiction of the course:

  • Definitions
  • Bipartite Graphs
  • Hamilton Cycles and Eulerian Circuits
  • Planar Graphs
    • Statement of Kuratowski's Theorem
  • Matchings in Bipartite Graphs
    • Hall's Theorem
  • Connectivity
    • Menger's Theorem
  • Extremal Graph Theory
    • Hamilton and other cycles
    • Turan's Theorem
  • Ramsey's Theorem
  • Graph Colourings
    • Chromatic Polynomial
    • Vizing's Theorem
    • Four-Colour and Five-Colour Theorems
      • Extensions to other surfaces
  • Eigenvalues
    • Applications to Strongly Regular Graphs
  • The Probabilistic Method
    • Lower bounds for Ramsey numbers
    • Graphs with large girth and chromatic number

Lecture series[edit | edit source]

List of Definitions

Assignments[edit | edit source]