Introduction to graph theory

## Contents

* 1 Introduction to Graph Theory
* 2 Course requirements
* 3 Course outline
* 4 Lecture series
* 5 Assignments

< Wikiversity < Wikiversity:School of Mathematics < School:Mathematics/Undergraduate/Pure Mathematics

## 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:

* knowledge of basic methods of proof
* knowledge of basic probability

## 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]

* Lecture 1 Introduction and Definitions
* Lecture 2 Bipartite Graphs and Trees
* Lecture 3 Hamilton Cycles and Eulerian Circuits
* Lecture 4 Graph Traversal
* Lecture 5 Flows and Cuts
* Lecture 6 Planar Graphs

List of Definitions

## Assignments[edit | edit source]

* Problems 1 (on Lectures 1-5)
* Problems 2 (on Lectures 6-10)