Cities joined by roads, computers joined by cables, people joined by friendships, web pages joined by links, tasks joined by "must finish before" constraints: all of these are made of things and connections between pairs of things. A graph is the mathematical model of exactly that, and it is probably the single most useful structure in computer science. Shortest-path routing, social network analysis, compiler register allocation and dependency resolution in package managers are all graph problems.
This chapter sets up the vocabulary used in every later graph chapter: types of graphs, degrees and the handshaking theorem, special families of graphs, bipartite graphs, subgraphs and complements, degree sequences, and paths and connectivity. Later chapters build on it: Graph Representations & Isomorphism, Euler & Hamiltonian Paths, Planar Graphs, Graph Coloring and Trees & Spanning Trees.
A graph G = (V, E) consists of a non-empty set V of vertices (or nodes) and a set E of edges, where each edge joins a pair of vertices called its endpoints. In a simple graph each edge is an unordered pair {u, v} of distinct vertices, and no two edges join the same pair.
Kinds of Graphs
Different problems need slightly different kinds of graph. The terms below are standard (they follow the usual textbook convention used in Indian university courses):
Type | Edges | Multiple edges? | Loops? | Example use |
|---|---|---|---|---|
Simple graph | Undirected | No | No | Friendship network |
Multigraph | Undirected | Yes | No | Several cables between two routers |
Pseudograph | Undirected | Yes | Yes | Road map with a loop road |
Directed graph (digraph) | Directed | No | Yes | Twitter-style "follows" |
Directed multigraph | Directed | Yes | Yes | State machine with several transitions |
A directed edge (u, v) goes from u to v; u is its initial vertex (tail) and v its terminal vertex (head). A directed graph with no loops (and no multiple edges) is a simple directed graph. A weighted graph attaches a number (distance, cost, capacity) to each edge. Unless we say otherwise, "graph" in this tutorial means a finite simple undirected graph.
Basic Terminology
Vertices u and v are adjacent (neighbours) if {u, v} is an edge. The edge is incident with u and v.
The neighbourhood N(v) is the set of all neighbours of v.
The degree deg(v) is the number of edges incident with v, where a loop counts twice (it touches v at both ends).
A vertex of degree 0 is isolated; a vertex of degree 1 is a pendant (or leaf).
δ(G) and Δ(G) denote the minimum and maximum degree.
In a digraph, the in-degree deg−(v) counts edges coming into v and the out-degree deg+(v) counts edges leaving v.
The number of vertices |V| is the order of G, and the number of edges |E| is its size.
The Handshaking Theorem
For every undirected graph G = (V, E) (multiple edges and loops allowed): ∑v∈V deg(v) = 2|E|.
Proof. Every edge has two ends. An edge {u, v} with u ≠ v adds 1 to deg(u) and 1 to deg(v); a loop at v adds 2 to deg(v). Either way each edge adds exactly 2 to the total, so the sum of degrees is 2|E|. ∎
The name comes from a party: if everyone counts how many hands they shook, the total is twice the number of handshakes, because each handshake involves two hands.
Corollary: odd-degree vertices come in pairs
Every graph has an even number of vertices of odd degree.
Proof. Split the degree sum into the sum over even-degree vertices plus the sum over odd-degree vertices. The total (2|E|) is even and the even-degree part is even, so the odd-degree part is even. A sum of odd numbers is even only when there is an even number of terms. ∎
For directed graphs the same counting gives ∑ deg−(v) = ∑ deg+(v) = |E|: each directed edge leaves exactly one vertex and enters exactly one vertex.
Worked examples
Example 1. Can 15 people at a meeting each shake hands with exactly 3 others? The degree sum would be 15 × 3 = 45, which is odd. But it must equal 2|E|, which is even. So it is impossible.
Example 2. A graph has 10 edges and every vertex has degree 4. How many vertices? 4n = 2 × 10, so n = 5. (K5, defined below, is such a graph.)
Example 3. A graph has 21 edges, 3 vertices of degree 4 and all other vertices of degree 3. Then 3·4 + 3k = 42, so k = 10 and the graph has 13 vertices.
Special Families of Graphs
Graph | Description | Vertices | Edges | Degrees |
|---|---|---|---|---|
Complete graph Kn | Every pair of vertices adjacent | n | n(n − 1)/2 | all n − 1 |
Cycle Cn (n ≥ 3) | v1v2…vn in a ring | n | n | all 2 |
Wheel Wn (n ≥ 3) | Cn plus a hub joined to every cycle vertex | n + 1 | 2n | hub n, others 3 |
Hypercube Qn | Bit strings of length n, adjacent if they differ in one bit | 2n | n · 2n−1 | all n |
Complete bipartite Km,n | Parts of size m and n, every cross pair adjacent | m + n | mn | n on one side, m on the other |
Path Pn | n vertices in a line | n | n − 1 | ends 1, others 2 |
Each edge count follows from the handshaking theorem. For Qn: 2n vertices of degree n give degree sum n · 2n, so n · 2n−1 edges (Q3, the cube, has 12; Q4 has 32). Hypercubes are used as interconnection networks in parallel computers.
K4 C5 W4 (hub h)
a ───── b a a ───── b
│ ╲ ╱ │ ╱ ╲ │ ╲ ╱ │
│ ╳ │ e b │ h │
│ ╱ ╲ │ │ │ │ ╱ ╲ │
d ───── c d ─── c d ───── c
K2,3 : parts {x, y} and {1, 2, 3}
edges x–1, x–2, x–3, y–1, y–2, y–3
A graph in which every vertex has the same degree k is k-regular. Kn is (n − 1)-regular, Cn is 2-regular and Qn is n-regular. By the handshaking theorem, a k-regular graph on n vertices has nk/2 edges, so nk must be even: there is no 3-regular graph on 7 vertices.
Bipartite Graphs
G is bipartite if V can be split into two disjoint sets X and Y such that every edge has one endpoint in X and the other in Y. Equivalently, the vertices can be coloured with two colours so that adjacent vertices get different colours.
Bipartite graphs model "two kinds of things": students and courses, jobs and machines, users and products. C6 and Qn are bipartite (in Qn, split by whether the number of 1-bits is even or odd); C5 and K3 are not.
Theorem. A graph is bipartite if and only if it contains no cycle of odd length.
Proof (⇒). Walking around a cycle, each edge switches between X and Y. To return to the starting side you need an even number of switches, so every cycle has even length.
Proof (⇐). It is enough to handle each connected component separately. Pick a vertex r and let d(v) be the length of a shortest path from r to v. Put vertices with even d(v) in X and odd d(v) in Y. Suppose some edge uv had both ends on the same side. For any edge, |d(u) − d(v)| ≤ 1, so the same parity forces d(u) = d(v). Then a shortest path r → u, the edge uv, and a shortest path v → r form a closed walk of odd length 2d(u) + 1. Any closed walk of odd length contains a cycle of odd length (split it at a repeated vertex; one of the two shorter closed walks is still odd, and repeat until no vertex repeats). This contradicts the assumption, so the split is valid. ∎
The proof is also an algorithm: run breadth-first search, give alternate levels alternate colours, and report "not bipartite" if some edge joins two vertices of the same colour. It runs in O(|V| + |E|) time.
A bipartite graph with parts of size k and n − k has at most k(n − k) edges, which is largest when the parts are as equal as possible: at most ⌊n²/4⌋ edges.
Subgraphs and Complements
H = (W, F) is a subgraph of G = (V, E) if W ⊆ V and F ⊆ E (and every edge in F has both ends in W).
A subgraph is spanning if it uses all of V.
The induced subgraph G[W] takes a vertex set W and keeps every edge of G whose ends both lie in W.
The complement Ḡ has the same vertices, and uv is an edge of Ḡ exactly when it is not an edge of G. So |E(G)| + |E(Ḡ)| = n(n − 1)/2.
The union G1 ∪ G2 has vertex set V1 ∪ V2 and edge set E1 ∪ E2.
Example. If G has 9 vertices and 20 edges, its complement has 36 − 20 = 16 edges. If degG(v) = d then degḠ(v) = n − 1 − d.
Degree Sequences
The degree sequence of a graph lists its vertex degrees in non-increasing order. A sequence is graphic if some simple graph has it as its degree sequence. An odd sum immediately rules a sequence out (handshaking), but an even sum is not enough. For example, (3, 3, 3, 1) has even sum 10, but it is not graphic: three vertices of degree 3 in a 4-vertex graph must each be adjacent to all other vertices, so the fourth vertex would have degree 3, not 1.
The Havel–Hakimi test
A non-increasing sequence (d1, d2, …, dn) is graphic if and only if the sequence obtained by deleting d1 and subtracting 1 from each of the next d1 terms is graphic.
Repeat (re-sorting each time) until you reach all zeros (graphic) or something impossible: a negative number, or a first term larger than the number of remaining terms (not graphic).
(4, 4, 3, 3, 2, 2)
remove 4, subtract 1 from next four → (3, 2, 2, 1, 2) → sort → (3, 2, 2, 2, 1)
remove 3, subtract 1 from next three → (1, 1, 1, 1)
remove 1, subtract 1 from next one → (0, 1, 1) → sort → (1, 1, 0)
remove 1, subtract 1 from next one → (0, 0) all zeros: GRAPHIC
(5, 5, 4, 3, 2, 1) sum 20 is even, but...
remove 5 → (4, 3, 2, 1, 0)
remove 4 → (2, 1, 0, −1) negative: NOT GRAPHIC
Intuition for the second one: two vertices of degree 5 in a 6-vertex graph are each adjacent to all other vertices, so every vertex has degree at least 2, yet one vertex is supposed to have degree 1.
Walks, Paths and Cycles
Textbooks use slightly different words here, so be careful in exams. This table uses the most common modern terms:
Term | Repeated vertices? | Repeated edges? | Closed (ends where it starts)? |
|---|---|---|---|
Walk | Allowed | Allowed | Either |
Trail | Allowed | No | Either |
Path | No | No | No |
Circuit (closed trail) | Allowed | No | Yes |
Cycle | No (except first = last) | No | Yes |
The length is the number of edges. (Rosen's textbook says "path" for what we call a walk, calls a path or circuit "simple" when it repeats no edge (our trail or circuit), and some older books call a closed trail a "cycle"; read each question's definitions.) A useful fact: if there is a walk from u to v, there is a path from u to v. Take the shortest walk; if it repeated a vertex, cutting out the loop between the two visits would give a shorter walk.
Connectivity
An undirected graph is connected if there is a path between every pair of vertices. The maximal connected subgraphs are called connected components.
A cut vertex (articulation point) is a vertex whose removal increases the number of components.
A bridge (cut edge) is an edge whose removal increases the number of components. An edge is a bridge exactly when it lies on no cycle.
The vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects G (or leaves a single vertex); the edge connectivity λ(G) is the minimum number of edges whose removal disconnects G. Whitney's inequality says κ(G) ≤ λ(G) ≤ δ(G). The right half is easy: deleting the δ edges at a minimum-degree vertex isolates it.
For digraphs: strongly connected means there is a directed path from every vertex to every other; weakly connected means the underlying undirected graph is connected.
How many edges force connectivity?
Theorem 1. A connected graph on n vertices has at least n − 1 edges.
Proof. Start with n isolated vertices (n components) and add the edges one at a time. Each edge joins at most two components into one, so it reduces the number of components by at most 1. To reach 1 component we need at least n − 1 edges. ∎
Theorem 2. A simple graph on n vertices with more than (n − 1)(n − 2)/2 edges is connected.
Proof. Suppose G is disconnected. Let A be one component with k vertices (1 ≤ k ≤ n − 1). There are no edges between A and the other n − k vertices, so G misses at least k(n − k) of the C(n, 2) possible edges. For 1 ≤ k ≤ n − 1, k(n − k) − (n − 1) = (k − 1)(n − k − 1) ≥ 0, so k(n − k) ≥ n − 1. Hence |E| ≤ C(n, 2) − (n − 1) = (n − 1)(n − 2)/2. ∎
The bound is tight: Kn−1 plus one isolated vertex is disconnected with exactly (n − 1)(n − 2)/2 edges. (For n = 5 that is 6 edges, and a brute-force search over all 1,024 graphs on 5 labelled vertices confirms that no disconnected one has more.)
Exploring a Graph in Python
We store, for each vertex, the set of its neighbours (other ways to store graphs are compared in the next chapter). The graph below has edges 1–2, 1–3, 2–3, 3–4, 4–5, 6–7 and an isolated vertex 8. The program computes degrees, checks the handshaking theorem, finds components with breadth-first search, and runs the BFS bipartite test from the proof above.
from collections import deque
edges = [(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (6, 7)]
vertices = range(1, 9) # vertex 8 is isolated
# Store the neighbours of each vertex
adj = {v: set() for v in vertices}
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
deg = {v: len(adj[v]) for v in vertices}
print("Degrees :", deg)
print("Sum of degrees :", sum(deg.values()), "= 2 x", len(edges))
print("Odd vertices :", [v for v in vertices if deg[v] % 2 == 1])
def components():
seen, comps = set(), []
for s in vertices:
if s in seen:
continue
comp, queue = [], deque([s])
seen.add(s)
while queue:
u = queue.popleft()
comp.append(u)
for w in adj[u]:
if w not in seen:
seen.add(w)
queue.append(w)
comps.append(sorted(comp))
return comps
def is_bipartite():
side = {}
for s in vertices:
if s in side:
continue
side[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for w in adj[u]:
if w not in side:
side[w] = 1 - side[u] # opposite side
queue.append(w)
elif side[w] == side[u]:
return False # edge inside one side
return True
print("Components :", components())
print("Bipartite? :", is_bipartite())
Output:
Degrees : {1: 2, 2: 2, 3: 3, 4: 2, 5: 1, 6: 1, 7: 1, 8: 0}
Sum of degrees : 12 = 2 x 6
Odd vertices : [3, 5, 6, 7]
Components : [[1, 2, 3, 4, 5], [6, 7], [8]]
Bipartite? : False
Four odd-degree vertices, an even number as promised. The graph is not bipartite because of the triangle 1–2–3. In this graph, 3 and 4 are cut vertices, and 3–4, 4–5 and 6–7 are bridges (none of them lies on a cycle).
Common Mistakes
Counting a loop once. A loop adds 2 to the degree of its vertex.
Thinking an even degree sum makes a sequence graphic. It is necessary, not sufficient; use Havel–Hakimi.
Mixing up subgraph and induced subgraph. An induced subgraph must keep every edge between the chosen vertices.
Path vs walk. A path may not repeat vertices. Check which definition the question uses.
Assuming a graph with n − 1 edges is connected. n − 1 edges are necessary for connectivity, not sufficient (a triangle plus an isolated vertex has 3 edges on 4 vertices).
Interview and GATE-Style Questions
Q1. What is the maximum number of edges in a disconnected simple graph with 10 vertices?
(n − 1)(n − 2)/2 = 9 · 8/2 = 36, achieved by K9 plus an isolated vertex.
Q2. Is (3, 3, 3, 3, 3, 3) graphic? Is (3, 3, 3, 3, 3) graphic?
(3, 3, 3, 3, 3, 3): yes (sum 18; for example K3,3, or the triangular prism). (3, 3, 3, 3, 3): no, the sum 15 is odd.
Q3. How many edges does K4,6 have? Is it regular?
4 × 6 = 24 edges. It is not regular: the 4 vertices have degree 6 and the 6 vertices have degree 4. Km,n is regular only when m = n.
Q4. A simple graph has 8 vertices and its complement has 10 edges. How many edges does it have?
C(8, 2) − 10 = 28 − 10 = 18.
Q5. Prove that in any group of two or more people, there are two people with the same number of friends in the group.
Model it as a simple graph on n ≥ 2 vertices. Degrees lie in {0, 1, …, n − 1}, but 0 and n − 1 cannot both occur (a vertex adjacent to everyone rules out an isolated vertex). So the n degrees take at most n − 1 values, and by the Pigeonhole Principle two vertices share a degree.
Q6. Is Q3 bipartite? Does it contain a triangle?
Yes, it is bipartite (split bit strings by the parity of their number of 1s). So it has no odd cycle, and in particular no triangle.
Summary
A graph is a set of vertices plus edges joining pairs. Simple graphs forbid loops and multiple edges; digraphs have directed edges.
Handshaking theorem: ∑ deg(v) = 2|E|, so the number of odd-degree vertices is even.
Key families: Kn (n(n − 1)/2 edges), Cn, Wn, Qn (n · 2n−1 edges), Km,n (mn edges).
Bipartite ⇔ no odd cycle; BFS 2-colouring tests it in linear time.
Havel–Hakimi decides whether a degree sequence is graphic.
Connected graphs need at least n − 1 edges; more than (n − 1)(n − 2)/2 edges guarantees connectivity.
We have been drawing graphs as pictures. Next, in Graph Representations & Isomorphism, we store them in a computer and ask when two different-looking graphs are really the same.