Counting

The four principles of counting: addition, multiplication, subtraction, and division. Examples.

Permutations and combinations

Permutations, number of different permutations. Subsets, number of different subsets. Binomial coefficients. Sum of binomial coefficients.

The pigeonhole principle

The pigeonhole principle. Sample applications. The Chinese remainder theorem.

Graphs: the basics

Definitions: graph, vertex, edge, loop, degree, path, cycle, directed and undirected graphs, connected and disconnected graphs, adjacency matrices.

Connectivity

Walks, trails, and paths. Connected and disconnected graphs. Disconnecting sets, cut sets, bridges, edge connectivity. Separating sets, vertex connectivity, k-connectivity.

Hamiltonian graphs

Hamiltonian cycles and Hamiltonian graphs. Ore's theorem.

Algorithms on graphs

Depth-first and breadth-first searches. Weighted graphs. The shortest path problem. Dijkstra's algorithm.

Trees

Trees as minimally connected graphs. Number of edges in a tree. Spanning trees. Kruskal's algorithm to find a minimal spanning tree.

Counting graphs

Graph isomorphism. How many non-isomorphic graphs are there? Counting trees: Cayley's formula.

Graph colorings

Coloring a graph. Bipartite graphs. Matchings and maximal matchings. Philip Hall's theorem.

Planar graphs

Planar graphs. Euler's theorem. Non-planarity of K_{3,3} and K_5.

Ramsey's theorem

Bringing together combinatorics and graphs: Ramsey's theorem.

Course review and problem session I

Course review. Exercises.

Eulerian graphs

Eulerian trails. Seven Bridges of Königsberg. Euler's theorem. Fleury's algorithm for constructing a Eulerian trail.

Final test

Final test