contents

1. BASIC CONCEPTS

Graphs: definitions.
Paths and circuits.
Connectivity.
Isomorphisms of graphs.

2. TREES AND FORESTS

Definition and properties.
ErdOs-Skekeres Theorem on Sequences.
Centers in trees. Rooted trees. Binary trees.
Spanning trees. The number of spanning trees. Cayley's Formula.
Matrix-Tree Theorem, application to electrical circuits.
Minimum cost spanning tree. Kruskal's and Prim's algorithms

3. EULERIAN PATHS AND HAMILTONIAN CIRCUITS

Fleury's algorithm. The Chinese Postman Problem.
The Traveling Salesman Problem.
Ranking the participants in a tournament.

4. NETWORKS

Flows. Edge cuts.
The Maximum Flow - Minimum Cut Theorem.
Theorems of Menger.

5. PLANAR GRAPHS

Embeddings in surfaces.
Euler's Formula.
Kuratowski's Theorem.
The Four-Color Conjecture.

6. GRAPH ALGORITHMS

Algorithm Efficiency.
Breadth-First Search Algorithm (BFS).
Depth-First Search Algorithm (DFS).
Connected Components.
Dijkstra's Shortest Path Algorithm and Bellman-Ford Shortest Path Algorithm.