Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines, the internet, electronic circuits and even molecular bonds. There are also social networks between friends and families. All these systems consist of certain points called
Graph theory is the study of graphs and their properties. It is one of the most exciting and visual areas of mathematics, and has countless important applications:
We can sketch the layout of simple graphs using circles and lines. The position of the circles and the length of the lines is irrelevant – we only care about how they are connected to each other. The lines can even cross each other, and don’t have to be straight.
In some graphs, the edges only go one way. These are called directed graphs.
Some graphs consist of multiple distinct segments which are not connected by edges. These graphs are disconnected.
Other graphs may contain multiple edges between the same pairs of vertices, or vertices which are connected to themselves (loops).
For simplicity we will only think about undirected and connected graphs without multiple edges and loops in this course
We can create new graphs from an existing graph by removing some of the vertices and edges. The result is called a subgraph. Here are a few examples of graphs and subgraphs:
Graphs which consist of a single ring of vertices are called cycles. All cycles have