Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Send us feedback!

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Glossary

Select one of the keywords on the left…

Graphs and NetworksIntroduction

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

Road and Rail Networks

Integrated Circuits

Supply Chains

Friendships

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.

Order:

Order:

Degree:

Degree:

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