Select one of the keywords on the left…

Graphs and NetworksIntroduction

Reading time: ~10 min

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 , some of which are connected by . In mathematics, this is called a graph.

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:

Road and Rail Networks

Integrated Circuits

Supply Chains


Neural Connections

The Internet

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 of a graph is its number of vertices. The degree of a vertex in a graph is the number of edges which meet at that vertex.





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