# Introduction

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 **graphs**

**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:

The **order****degree**

Order:

Order:

Degree:

Degree:

Graphs which consist of a single ring of vertices are called **cycles**. All cycles have