February 18, 2012 – Dr. Branislav Kisačanin – “Introduction to Graph Theory”

February 18, 2012 – Dr. Branislav Kisačanin – “Introduction to Graph Theory”

Graph theory was born when Leonhard Euler solved the Seven Bridges of Koenigsberg problem and has since grown into a mathematical discipline with beautiful theoretical results and with applications in disciplines like theory of dynamic systems, electrical engineering, computer vision, neuroscience, and social networking.

In this lecture we will learn about the fascinating early history of the graph theory, discuss Eulerian and Hamiltonian paths, node and edge coloring, and look at other important properties of graphs, such as planarity. We will even work on several problems like this one from the Sixth IMO (Moscow, 1964):

Each of 17 students talked with every other student. Each pair of students talked about one of three different topics. Prove that there are three students that talked about the same topic among themselves.

Advertisement