Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 36 ยท Getting Started

What Is a Graph?

Meet graphs in graph theory: vertices, edges, and why dots-and-lines models road maps, friendships and networks. Build your first graph in Python and answer simple questions.

A graph is one of the simplest ideas in mathematics and one of the most useful. It is a collection of points and a collection of connections between pairs of points. That is all. Yet this tiny definition describes road networks, friendships on a social site, links between web pages, dependencies between software packages, molecules, electrical circuits and the routes of airplanes.

In this tutorial you will learn the language of graphs, the classic algorithms on them, and the famous theorems behind them. Every idea is implemented from scratch in Python so you can run it, change it and see what happens. Where it helps, we compare our code with the networkx library, which also runs in the page.

Every <TryIt> on this site runs real Python (Pyodide) in your browser. The first run downloads the runtime, so it can take a few seconds. numpy, scipy, sympy and networkx load automatically when you import them.

Points and connections

Picture five friends: Ana, Ben, Cy, Di and Eli. Ana knows Ben and Cy. Ben knows Cy. Cy knows Di. Di knows Eli. Draw each person as a dot and each friendship as a line between two dots, and you have a graph.

graph LR
  Ana --- Ben
  Ana --- Cy
  Ben --- Cy
  Cy --- Di
  Di --- Eli

Five people, five friendships: a graph with 5 vertices and 5 edges.

The picture is only a drawing. The graph itself is the information who is connected to whom. You could move the dots anywhere and it would be the same graph.

The formal definition

A graph G = (V, E) consists of:

  • a set V of vertices (also called nodes), and
  • a set E of edges (also called links), where each edge joins two vertices.

In the friendship graph, V = {Ana, Ben, Cy, Di, Eli} and E = {Ana-Ben, Ana-Cy, Ben-Cy, Cy-Di, Di-Eli}. We write |V| for the number of vertices (often called n) and |E| for the number of edges (often m). Here n = 5 and m = 5.

An edge between u and v is written {u, v} (an unordered pair) when direction does not matter, or (u, v) when it does. We meet directed graphs in kinds of graphs. For now every edge is two-way.

Two vertices joined by an edge are adjacent or neighbors. An edge and a vertex it touches are incident.

Your first graph in Python

The simplest honest representation is a set of vertices and a set of edges. Because edges are unordered, we store each as a frozenset.

Python A graph as vertices and edges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that adjacent and neighbors are questions about the graph, not about the picture. Almost all of graph theory is about answering such questions quickly and about proving what is always true.

Why graphs are everywhere

A graph models any situation where things are related to other things:

Situation Vertices Edges
Road map Intersections Road segments
Social network People Friendships or follows
The web Pages Hyperlinks
Chemistry Atoms Bonds
Scheduling Tasks "Must happen before"
Tournaments Teams Games played

Once you have turned a problem into a graph, you can use ready-made tools. "Is there a way to get from A to B?" becomes a path question. "What is the cheapest way?" becomes shortest paths. "Can we give the vertices colors so connected ones differ?" is a coloring question that we tackle later in the track.

The same graph with networkx

networkx is the standard Python library for graphs. We will build everything ourselves first, but it is useful to see the library version so you can recognize it.

Python The same graph in networkx

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

add_edges_from created the vertices automatically. A graph needs no special "vertex object": any hashable value (a string, a number, a tuple) can be a vertex.

Common mistakes

  • Confusing the graph with its drawing. Crossing lines do not mean extra vertices. Different drawings can show the same graph.
  • Mixing up "graph" and "chart". In this tutorial a graph is a network of vertices and edges, not a bar chart.
  • Forgetting that edges are pairs. An edge always involves exactly two vertices (they may be the same vertex in a loop, covered later).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A graph G = (V, E) has V = {a, b, c, d} and E = {ab, bc}. How many vertices and edges does it have?

    n = |V| = 4 counts every listed vertex, including the isolated d. m = |E| = 2 counts the edges ab and bc.
  2. 2. Two vertices joined by an edge are called:

    Adjacent (neighbors) describes two vertices joined by an edge. Incident describes a vertex and an edge that touches it.
  3. 3. You redraw a graph so that the dots sit in different places. What happened to the graph?

    A graph is defined by which vertices are connected, not by where they are drawn.
  4. 4. Which of these is a natural model for a graph?

    Cities as vertices and highways as edges form a graph. Graph theory studies exactly such networks.

Summary

  • A graph G = (V, E) is a set of vertices and a set of edges joining pairs of vertices.
  • n = |V| is the number of vertices and m = |E| the number of edges.
  • Adjacent vertices are joined by an edge; an edge is incident to the vertices it touches.
  • A drawing is only one picture of a graph; the connections are what matter.
  • Graphs model roads, friendships, web links, molecules, schedules and much more.

Next: Graph Terminology