Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 68 · Graph Theory

Graphs: Terms and Representations

Learn graph vocabulary, degree, the handshake lemma and special graphs, then store graphs as adjacency lists and matrices in plain Python.

A graph is the simplest model of connection: some things, and some links between them. Cities and roads, people and friendships, web pages and hyperlinks, courses and prerequisites, computers and cables all fit. Once a problem is phrased as a graph, a whole toolbox of ideas (paths, trees, colorings, flows) applies to it, whatever the original subject was.

This lesson sets the vocabulary and shows two standard ways to store a graph in a program. We build everything with plain Python dictionaries, lists and sets, with no graph library, so every term has a few lines of code behind it. The data-structure view of the same ideas is in Graphs in the DSA track and Graph Representations; here the focus is the mathematics.

A graph is two sets

Vertices The things. Also called nodes.
Edges The links between pairs of vertices.
G = (V, E) Write a graph as its vertex set and edge set.
1 / 2

Vertices, edges and the basic terms

A graph G = (V, E) consists of a set V of vertices and a set E of edges. In an undirected graph an edge is an unordered pair {u, v}: the link works both ways, like a friendship. In a directed graph (digraph) an edge is an ordered pair (u, v): an arrow from u to v, like "follows" on a social site.

A few more words you will meet constantly:

  • Two vertices joined by an edge are adjacent or neighbors. The edge is incident to both of its endpoints.
  • A loop is an edge from a vertex to itself. Parallel edges (multi-edges) connect the same pair more than once. A graph with neither is simple. Unless said otherwise, this tutorial uses simple graphs.
  • A weighted graph attaches a number (distance, cost, capacity) to every edge.
  • The number of vertices is written |V| (often n) and the number of edges |E| (often m).

The degree of a vertex, deg(v), is the number of edges touching it. In a directed graph we split it into in-degree (arrows arriving) and out-degree (arrows leaving).

The handshake lemma

Add up the degrees of every vertex in an undirected graph. Each edge has two endpoints, so each edge contributes exactly 2 to the total:

sum of deg(v) over all v = 2 · |E|

This is the handshake lemma: if every guest at a party counts the hands they shook, the grand total is twice the number of handshakes. Two consequences are useful in proofs and puzzles:

  1. The degree sum is always even.
  2. Therefore the number of vertices with odd degree is even. A party can never have exactly three people who shook an odd number of hands.

The same idea gives a quick edge count. A graph where every vertex has degree 3 and which has 10 vertices must have 3 · 10 / 2 = 15 edges.

Storing a graph: the adjacency list

An adjacency list maps each vertex to the collection of its neighbors. In Python a dictionary of sets is natural: lookups like "is b a neighbor of a?" are fast, and duplicates are impossible, which keeps the graph simple.

Storing an undirected edge means recording it in both directions. Memory use is proportional to n + m, which is small for sparse graphs (few edges compared to n²), the common case for real networks.

Python An undirected graph as an adjacency list

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.

The degree sum is 10 and there are 5 edges, so the handshake lemma checks out. A, B and D have degree 2, C has 3 and E has 1, so the odd-degree vertices are C and E, a pair, as the lemma promises.

Storing a graph: the adjacency matrix

An adjacency matrix is an n × n grid where entry [i][j] is 1 if there is an edge from vertex i to vertex j and 0 otherwise. For an undirected graph the matrix is symmetric (entry [i][j] equals entry [j][i]), and the sum of row i is the degree of vertex i. For a weighted graph, store the weight instead of 1.

A matrix always uses n² cells, so it wastes space on sparse graphs, but it answers "is there an edge between i and j?" in one step, and matrix arithmetic gives surprising results: the entry [i][j] of the matrix multiplied by itself counts the walks of length 2 from i to j, a trick we use in Paths, Cycles and Connectivity.

Python From adjacency list to matrix, and directed degrees

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.

For directed graphs the handshake lemma becomes: the sum of in-degrees equals the sum of out-degrees, and both equal |E|, because every arrow has exactly one tail and one head.

Special graphs worth knowing

A handful of families appear again and again, and you should know their sizes by heart:

Graph Notation Description Edges
Complete graph K_n every pair of vertices is adjacent n(n-1)/2
Path P_n vertices in a line n - 1
Cycle C_n a path whose ends are joined (n ≥ 3) n
Star S_n one center joined to n leaves n
Complete bipartite K_{m,n} two groups, every cross pair adjacent m · n

The complete-graph formula is a combination count: an edge is a choice of 2 vertices out of n, and there are C(n, 2) = n(n-1)/2 of those (see Permutations and Combinations). A graph is bipartite when its vertices split into two groups with every edge going between the groups; K_{m,n} is the extreme case. We test bipartiteness in Graph Coloring and Planarity.

Other useful notions: a subgraph keeps some of the vertices and edges; the complement of a simple graph has an edge exactly where the original has none; a graph is regular if all degrees are equal; and a dense graph has close to n²/2 edges.

Python Building special graphs and checking their edge counts

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.

Cycles and complete graphs are regular, so every degree in the output is the same. The complement of the 5-cycle turns out to be another 5-cycle, a small surprise worth remembering.

A catalogue of graph types

Graph theory uses a lot of adjectives. Here is the full vocabulary in one place, grouped by what each word describes.

What the edges look like

  • Simple graph: undirected, no loops, no parallel edges. Our default.
  • Multigraph: allows several edges between the same pair (the Königsberg bridges).
  • Pseudograph: allows loops (an edge from a vertex to itself) as well as parallel edges. A loop adds 2 to a vertex's degree.
  • Directed graph (digraph): each edge has a direction. Weighted graph: each edge has a number such as a cost.

How many edges there are

  • Null graph: no edges. Complete graph K_n: every pair joined.
  • Sparse graph: the edge count is close to the vertex count (road maps, trees). Dense graph: the edge count is close to the maximum n(n-1)/2. The density 2m / (n(n-1)) runs from 0 to 1, and sparse graphs are best stored as adjacency lists.

How uniform it is

  • k-regular graph: every vertex has degree k. Then the handshake lemma gives m = n·k/2, so n·k must be even. A 3-regular graph needs an even number of vertices.
  • Cycle C_n is 2-regular, K_n is (n-1)-regular, and the Petersen graph is 3-regular on 10 vertices (15 edges).
  • Wheel W_n: a cycle on n - 1 vertices plus a hub joined to all of them, with 2(n - 1) edges.
  • Hypercube Q_k: vertices are the k-bit strings, joined when they differ in one bit. It has 2^k vertices, is k-regular and has k · 2^(k-1) edges.
  • Complete multipartite graph: vertices split into groups and every pair from different groups is adjacent (K_{m,n} has two groups).
Python Edge counts, regularity and density for the catalogue

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.

The wheel and hypercube counts match their formulas, the Petersen graph is regular of degree 3, and the loop in the pseudograph is counted twice, so the degree sum is still twice the number of edges.

Choosing a representation

Use an adjacency list when the graph is large and sparse, when you mostly loop over neighbors (traversals, shortest paths), and when edges come and go. Use an adjacency matrix when the graph is small or dense, when you need constant-time edge lookups, or when matrix algebra is the point. A third option, a plain edge list (a list of pairs), is the easiest format for input files and for algorithms like Kruskal's that sort edges.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. An undirected graph has 7 vertices, each of degree 4. How many edges does it have?

    By the handshake lemma the degree sum is 7 x 4 = 28, which equals twice the number of edges, so there are 14 edges.
  2. 2. Which degree list can NOT belong to a simple undirected graph?

    Three vertices of degree 1 give a degree sum of 3, which is odd. The sum must equal twice the number of edges, so it has to be even.
  3. 3. How many edges does the complete graph K_8 have?

    Each edge is a choice of 2 vertices out of 8: C(8, 2) = 8 x 7 / 2 = 28.
  4. 4. Which statement about the adjacency matrix of an undirected simple graph is true?

    An edge {u, v} sets both [u][v] and [v][u], so the matrix is symmetric. A simple graph has no loops, so the diagonal is all zeros.
  5. 5. In a directed graph with 12 edges, what is the sum of all out-degrees?

    Every edge leaves exactly one vertex, so the out-degrees add up to the number of edges, 12 (and so do the in-degrees).

Summary

  • A graph G = (V, E) has vertices and edges; edges are unordered pairs (undirected) or ordered pairs (directed). Simple graphs have no loops or parallel edges.
  • The degree of a vertex counts its incident edges; the handshake lemma says the degrees add up to 2|E|, so the number of odd-degree vertices is always even.
  • An adjacency list stores neighbors and suits sparse graphs; an adjacency matrix gives instant edge lookups and supports matrix algebra.
  • Know the families K_n, P_n, C_n, stars and K_{m,n} and their edge counts.
  • In a directed graph, in-degrees and out-degrees each sum to |E|.

Next: Paths, Cycles and Connectivity, where we ask which vertices can reach which.