Graphs and Algorithms

It is better to solve one problem five different ways, than to solve five problems one way.

- George Pólya

Education is not preparation for life; education is life itself.

- John Dewey

Graph theory is an area of discrete mathematics that deals with objects called graphs. Since it is a very broad area, the purpose of these notes is only to get students used to working with graphs and how their mathematical properties are proved. We do not aim to provide a comprehensive treatment of the subject. Our goal is to present a few selected highlights that are simple to state and have interesting connections to algorithms.

📄️ Introduction

An (undirected) graph $G=(V,E)$ is a pair of vertex set $V$ and edge set $E$. Sometimes, we define only graph $G$ and use $V(G)$ and $E(G)$ to denote the set of vertices and edges respectively. An edge is an unordered pair of distinct vertices.

🗃️ Graph classes and isomorphisms

2 items

🗃️ Some structured graphs

2 items

🗃️ Directed graphs

2 items