Combinatorics and graph theory

Objectives and outcomes

Students will learn to classify combinatorics problems and solve them using known combinatorial methods.


Graphs and subgraphs. Adjacency matrix and incidence matrix. Graph invariants. Paths and cycles – a
more detailed approach. Cyclomatic number of a graph.  Trees and their applications. Hamiltonian and Euler cycles and their application. Graph coloring – a more detailed approach. Planar and polyhedral graphs. Kuratowski-Pontryagin Theorem. Coloring of planar graphs. Graph matching and applications. Independent sets, coverings and cliques. Stability in a graph with the use in Code Theory. Use in Linear Algebra. Power of square matrix and Markov chains. Signal flow graphs. Ramsey graph theory. Oriented graphs, block designs, finite geometries and matroids.

Practical classes

Solving tasks.