Introduction to Graph Theory

What is Graph Theory?

Graph Theory studies how things are connected, through a network of points and lines.

A graph looks like this:

A simple graph
An Example Graph

Yes, it is called a "graph"... but it is NOT this kind of graph:

not a line graph

They are both called "graphs". But they are different things. Just how it is.

This subject explores how these points and lines relate to each other, and how to best travel around them.

subway map

You can think of it as places and roads, or as stations and trains ... or as a map of friendships where each person is a node and each friendship is an edge.

There are many ways to think about graphs!

Graphs have applications in many areas such as computer science, biology, social sciences, transport and more.

Let's learn some special words:

  • A point is called a vertex (plural vertices)
  • A line is called an edge.
  • The whole diagram is called a graph.
  graph vertex and edge
graph degree 3 and 2
graph simple path and euler path

A Simple Path is like finding a way to visit every friend's house exactly once.

An Euler Path is like a mail carrier's route that goes down every street once.

Some Examples:

graph example 2

This Graph has:

  • 5 vertices: A, B, C, D and E
  • 8 edges: AB, BC, CD, DA, AE, BE, AC and BD
  • Vertices A and B have degree 4
  • Vertices C and D have degree 3
  • Vertex E has degree 2
graph example 3

This Graph has:

  • 6 vertices: A, B, C, D, E and F
  • 10 edges: AB, BC, CD, DA, AF, BF, CF, DF, AE and BE
  • Vertices A, B and F have degree 4
  • Vertices C and D have degree 3
  • Vertex E has degree 2

Real-World Uses

In the real world, we can find many situations that can be represented using graph theory:

Graph theory can help in planning the most efficient public transportation routes or managing network traffic on the internet.


There are many types of graphs such as directed and undirected graphs, weighted graphs, and algorithms that can solve fascinating problems like finding the shortest path between two points.