Graph Theory

1 Introduction

Graphs: A graph is a mathematical structure used to model pairwise relationships between

objects. Formally, a graph G is defined as an ordered pair G = (V, E), where V is a set of
vertices (also called nodes), representing the objects in the graph and E is a set of edges, repre-
senting the connections between the vertices. Each edge is either an unordered pair {u, v} (in
an undirected graph) or an ordered pair (u, v) (in a directed graph), where u, v ∈ V .

Simple Graphs: A graph is simple if between every two vertices there is at most one edge and
there are no loops (edges between v and itself).

Endpoints: For an edge uv, u and v are called it’s endpoints.

Adjacent Vertices: Two vertices are adjacent if there is an edge between them. They may
also be called connected vertices or neighbours.

Adjacent Edges: Two edges are adjacent if they share a common endpoint.

Incident Edges: An edge is said to be incident on a vertex if it has that vertex as an endpoint.

Degree: The degree of a vertex is the number of edges incident to (i.e., connected to) that
vertex. The degree represents how many edges are connected to the vertex. The degree of a
vertex v ∈ V is typically denoted by d(v)

Maximal and Minimal Degrees: The maximal degree of a graph G is typically denoted
by ∆(G) and the minimal degree by δ(G).

Trail: A trail from v to w is a sequence of vertices: v = v1 , v2 , ..., vn = w such that vi vi+1 ∈ E

for i = 1, 2, ..., n − 1.

Walk: A walk from v to w is a trail in which all edges are distinct.

Path: A path from v to w is a trail in which all vertices are distinct.

Length: The length of a trail / walk / path is the number of (not necessarily distinct) edges in it.

Distance: the distance between two vertices u and v in a graph is defined as the length
of the shortest path connecting u and v. The distance is typically denoted as: d(u, v).

Closed Trail: A closed trail is a sequence of vertices v1 , v2 , ..., vn such that vi vi+1 ∈ E for
i = 1, 2, ..., n, with indices taken cyclically. A closed trail has the same first and last vertices.

Circuit: A circuit is a closed trail in which the edges vi vi+1 are pairwise distinct.

Cycle: A cycle is a circuit in which the vertices are pairwise distinct.

Length: The length of a circuit / cycle is the number of edges in it.

Girth: The girth of a graph is the length of the minimal cycle.

Note: If no cycles exist in the graph, then the girth is said to be ∞.

1
Connected Graph: A connected graph is a type of graph in which there is a path between
every pair of vertices. This means that, for any two vertices u and v in the graph, there exists
a sequence of edges that connects them, ensuring that no vertex is isolated from the rest of the
graph.

Connected Components: Graphs that are not connected are simply a collection of con-
nected graphs.

Tree: Trees are connected graphs with no circuits.

Complement Graph: Given a graph G, its complement G consists of the same vertices
and exactly the edges that are not in G.

Regular Graphs: A graph is called regular if the degree of all the vertices is the same.

Complete Graphs: A complete graph is a type of graph in which every pair of distinct
vertices is connected by a unique edge. A complete graph with n vertices is denoted by Kn .

Bipartite Graphs: A bipartite graph is a graph whose vertex set can be divided into two
disjoint subsets such that no two vertices within the same subset are adjacent. In other words,
all edges in a bipartite graph connect a vertex from one subset to a vertex in the other subset.

Complete Bipartite Graphs: A complete bipartite graph is a special type of bipartite graph
in which every vertex in one subset is connected to every vertex in the other subset. A complete
bipartite graph is denoted as Km,n , where m is the number of vertices in the first subset, and
n is the number of vertices in the second subset.

Isomorphic Graphs: Isomorphic graphs are graphs that are structurally identical in the
sense that there is a one-to-one correspondence between their vertices and edges that preserves
the adjacency relationship. Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are said to be isomor-
phic if there exists a bijection (one-to-one and onto mapping) f : V1 → V2 such that:

{u, v} ∈ E1 if and only if {f (u), f (v)} ∈ E2

This means that the graphs have the same structure, but possibly with different labels for
vertices or edges.

Subgraph: A subgraph is a graph formed from a subset of the vertices and edges of an-
other graph.

Induced Subgraph: A subgraph H of G is called an induced subgraph if it includes all

edges of G that connect any pair of vertices in VH . In this case, H is defined by a subset of
vertices, and the edges between them are preserved.

Spanning Subgraph: A subgraph H of G is called a spanning subgraph if VH = VG . It

contains all the vertices of G, but may include only some of the edges.

Techniques Used in Graph Theory:

• Pigeonhole Principle: The pigeonhole principle comes in handy when we have a lot of
edges and want to find something like a complete subgraph.

2
Proposition: In any graph on 6 vertices, there exist three vertices that are pairwise connected
or three that are pairwise not connected.

Proof. Consider a graph G with 6 vertices, and choose an arbitrary vertex v. This vertex v
is either connected by edges to at least 3 other vertices or not connected to at least 3 other
vertices. This conclusion follows directly from the Pigeonhole Principle, since v has 5 other
vertices available, and we can divide the relationships into two categories: “connected” or “not
connected.”

• Double Counting: The technique of double counting consists of expressing something

in two different ways and then deducing that the results are equal.
X
Handshaking Lemma: In every graph G = (V, E); d(v) = 2|E|
v∈V

Proof. The LHS counts edges: d(v) counts those edges that are incident on v. But we can easily
observe that each edge uv is counted twice, once for d(v), and once for d(u). The conclusion
follows.

• Induction: Applying induction on vertices or edges or any other suitable parameter often
proves to be a great way to prove a statement.

Proposition: A tree on n vertices has n − 1 edges.

Proof. We prove the proposition by induction:

Base Case (n = 1): A tree with 1 vertex has 0 edges, which is 1 − 1 = 0. The base case
holds.

Inductive Step: Assume a tree with k vertices has k − 1 edges. Consider a tree with k + 1
vertices. Since a tree is connected and acyclic, it has at least one leaf (a vertex of degree 1).
Remove this leaf; the resulting tree has k vertices and, by the inductive hypothesis, k − 1 edges.
Adding the leaf back adds one vertex and one edge, giving k edges in total.

Conclusion: By induction, a tree with n vertices has n − 1 edges.

Corollary: A connected graph on n vertices has at least n − 1 edges.

Proof. If an edge belongs to a cycle, we can just remove it and the graph remains connected.
We can thus remove edges until we are left with a tree, which has n − 1 edges.

• Greedy Algorithms: Very often when we want to find some object in a graph, whether
a path, circuit or something else with some property, the easiest thing to do is to build it,
that is, start from a vertex and build it.

Proposition: Let G be a graph with minimal degree δ, then G contains a path of length δ
(having δ edges).

Proof. We just start from a vertex and build the path, at each point going to a new vertex if
possible. We thus obtain the path:

v1 , v2 , ..., vk

with no possibility of extension. This means that the neighbours of vk have to be amongst
v1 , v2 , ..., vk−1 . As k has atleast δ neighbours, we get δ ≤ k − 1, which implies the length of the
path is atleast δ.

3
Theorem: A finite graph is bipartite if and only if every cycle has even length.

Proof. If G is bipartite, consider a cycle v1 , v2 , ..., vr , v1 . We can assume v1 ∈ A (The first of

the two disjoint sets.) It follows that v2 ∈ B(The second of the two disjoint sets), v3 ∈ A and
so on. Hence vr is in B if and only if it if r is even. But vr is connected to v1 , so it is in B. It
follows that r is even.

Conversely, assume every cycle is even. It is enough to prove the statement for connected
graphs, as for non-connected ones we can put connected components together.

Pick a vertex v. The idea is that if we put v in A, its neighbours have to be in B, the
neighbours of neighbours have to be in A and so on. This forces us to define the sets in the
following way:

A = {w : d(v, w) is even} B = {w : d(v, w) is odd}

Obviously, A and B partition the graph, so we only need to show that we don’t have any
edge in one of the sets. Assume we had such an edge uw. Fix shortest paths from v to both u
and w and suppsose that the vertex farthest from v that these paths share is v ′ . Then putting
together the two paths from v ′ to u and v ′ to w, which have the same parity, with the edge uw,
we get an odd cycle, a contradiction. Hence the graph is bipartite.

• Exchanging Paths: The following method relates to building a new path from a given
one.

Proposition: Let G be a graph with minimal degree δ. If the length of the longest path in G
is δ, then G is a union of disjoint copies of Kδ+1 s.

Proof. Let G be a graph with minimum degree δ, and let the length of the longest path in G
be δ. Consider an arbitrary longest path in G, say P = v1 , v2 , . . . , vδ+1 . Since P is a longest
path, no vertex outside P can be connected to any vertex of P without extending P , which is
impossible by assumption.

Consider any vertex vi on the path P . Since G has minimum degree δ, each vertex must
be adjacent to at least δ other vertices. Since P has δ + 1 vertices and no vertex can be adjacent
to a vertex outside of P , it follows that each vertex on P is connected to all other vertices on
P.

Thus, the subgraph induced by the vertices of P is a complete graph Kδ+1 . By applying
the same argument to every component of G, we conclude that G is a disjoint union of complete
graphs Kδ+1 .

• Counting Edges: This technique revolves around figuring out the number of edges that
satisfy a particular property to get reasonable bounds or other fruitful information.

Proposition: The maximum number of edges that a triangle - free graph on n vertices can
have is: ⌊n2 / 4⌋.

Proof. Let G be a triangle-free graph. We want to deduce something about degrees from this.
The natural observation is that for any edge uv, u and v have no neighbours in common, oth-
erwise it would form a triangle. It follows that d(u) + d(v) ≤ n.

4
If this inequality held for any vertices v and u, whether connected or not, we would be easily
done, by summing over all u and v. We can try, though, to sum over all the edges and see what
happens: We have
X
(d(u) + d(v)) ≤ |E|n.
uv edge

But now we observe that in the left hand side, each summand d(u) occurs exactly d(u) times,
once for each edge incident on u. Using the Cauchy Schwarz inequality, we get:
X X
d(u) · d(u)
X X u u 4|E|2
(d(u) + d(v)) = d(u)2 ≥ =
u
n n
uv edge

4|E|2
 2
n
It follows that |E|n ≥ =⇒ |E| ≤ .
n 4
This is attained for the complete bipartite graph: K⌊n/2⌋,⌈n/2⌉ .

Proposition: Let G = (V, E) be a graph on n vertices and s an integer, 1 < s < n. If the
number of edges |E| is greater than (n(n − 1) / s), then G has a cycle of length at most s.

Proof. Assume the contrary, it follows tat the induced subgraph on any set of s vertices has no
cycle, which means it is a collection of disjoint trees, so it has atmost s − 1 edges.

We will now sum over all sets of s−vertices to get:

 
X n
(no. of edges in the subgraph induced on v1 , v2 , ..., vs ) ≤ (s − 1)
v1 ,v2 ,...,vs
s

On the other hand, in the left hand side each edge is counted n−2 Cs−2 times, as we just have to
choose the remaining s − 2 vertices. This means that the left hand side is equal to |E|n−2 Cs−2 .
Substituting we get:
   
n n−2 n(n − 1)
(s − 1) ≥ |E| =⇒ ≥ |E|, a contradiction.
s s−2 s
It follows that there exists a cycle of length at most s.

• Extreme Principle: The idea of the extreme principle is to take an object that is in some
sense the maximal or minimal. This principle can often be applied where it is intuitive
that the object we are looking for has some property of minimality or maximality.

Proposition: Let G be a graph, then if G has a circuit, then it has a cycle.

Proof. Take the shortest circuit: v1 , v2 , ..., vk , v1 .

If it is not a cycle, then vi = vj for some i ̸= j. It follows that: vi , vi+1 , ..., vj−1 , vi is a
shorter cicuit, a contradiction.

Proposition: Let G be a connected graph, then we can remove a vertex such that G remains
connected.

5
Proof. We are looking for a vertex that is not essential for the connectivity of the graph - it has
to be ’on the margin’. An idea is to take the longest path and look at one of its end vertices.
Such a vertex should capture the idea of ’on the margin’, as it cannot be connected to any
vertex outside the path.

There may be more than one longest paths, so just take one of them: v1 , v2 , ..., vr

We will prove that we can remove vr and keep the graph connected - in other words, that
G\{vr } is connected. Given the path cannot be extended, vr is adjacent to only the vertices in
the path.

Take two vertices u and v. There is a trail between them in G. If it does not contain vr ,
it is a trail in G\{vr }. Else if vr appears in the trail, it is preceded by vi and succeeded by vj
in that trail, for some i, j < r. But clearly there is a path between vi and vj , vi , vi+1 , ..., vj if
i < j, not involving vr . Hence we can replace vr in the trail from u to v, which implies that
there is a trail between u and v not involving vr .

• Trading Edges: This method may be applied when we want to prove that a graph has
a subgraph with a certain property, one may get lucky and display the subgraph directly,
or we may gradually modify the subgraph by adding and removing edges, until we get the
desired result.

Proposition: Let G be a connected graph with an even number of vertices. Then G has a
spanning subgraph such that all degrees are odd (in other words, we can select a number of
edges such that any any vertex of G is incident on an odd number of them).

2 Eulerian Circuits and Hamiltonian Cycles

Eulerian Circuit: A eulerian circuit is a circuit that uses every edge exactly once

Theorem: A graph contains an eulerian circuit if and only if every vertex has an even de-
gree.

Hamiltonian Cycle: In a graph G, a hamiltonian cycle is a cycle that passes through each
vertex exactly once.

Hamiltonian Path: A hamiltonian path is a path that passes through every vertex exactly
once.

Hamiltonian Graph: G is called a hamiltonian graph if it contains a hamiltonian cycle.

Theorem: Let G be a graph on n vertices. If for any two non-adjacent vertices v, w we

have d(v) + d(w) ≥ n, then G has a hamiltonian cycle.

Note: The above condition is not a necessary one, meaning that if it is not satisfied then
there may still exist a Hamiltonian cycle.

Remark: The path exchange technique is the key instrument when dealing with hamiltonian
paths or cycles.

6
3 Trees
Theorem: For a graph G with n vertices, the following statements are equivalent:

1. G is a tree.

2. G is a connected graph with n − 1 edges.

3. For any 2 vertices u and v in G, there is a unique path from u to v.

4. G is connected and the removal of any edge from G disconnects the graph.

Spanning Trees: A spanning tree of a graph is a connected acyclic subgraph that includes all
the vertices of the graph with exactly n − 1 edges, where n is the number of vertices.

Theorem: Any connected graph has a spanning tree, that is, a subgraph that is a tree con-
taining all vertices.

Proposition: Let G be a connected graph. Let T be a subgraph of G that is a tree (not

necessarily spanning). Then T can be extended to a spanning tree.

Proposition: Ig G is a connected graph, then there exists a vertex whose removal does not
disconnect the graph.

Proposition: Let G be a connected graph in which there are only two vertices whose re-
moval does not disconnect the graph, then G is just a path.

Proposition: Any connected graph with an even number of vertices has a spanning sub-
graph in which all the degrees are odd.

Theorem: Kn has nn−2 spanning trees.

Idea: For any tree, we will try to characterize it in order to be able to build it from that
characterization. The way we will do this is by removing leaves one by one and trying to write
down what we remove. We will have to do that in a well defined order though.

Prufer Code: In graph theory, a Prufer code is a sequence that uniquely represents a la-
belled tree with n vertices. It is particularly useful in combinatorics and is often used to count
labelled trees (via Cayley’s formula) and solve problems involving tree encoding and decoding.

4 Chromatic Numbers
Chromatic Numbers: Let G be a graph, the chromatic number of G is the minimum number
of colours required to colour the vertices of the graph such that no two adjacent vertices have
the same colour. The Chromatic Number is typically denoted as: χ(G).

Proposition: For any n, χ(Kn ) = n.

Proposition: A bipartite graph with atleast one edge has χ(G) = 2.

Proposition: Let G be a graph, then χ(G) ≤ ∆(G) + 1, where ∆(G) is the maximal de-
gree of G.

7
Proposition: Let G be a graph on n vertices and G its complement, then: χ(G)χ(G) ≥ n.

5 Planar Graphs
Planar Graphs: A graph is planar if it can be drawn in the plane such that its edges do not
intersect in their interior.

Face: A face refers to a region enclosed by edges of a planar graph when the graph is drawn
on a plane without any of its edges crossing.

Euler’s Formula: Consider a planar drawing of a connected graph G(V, E), and denote by
|F | the set of faces. Thes we have: |E| = |V | + |F | − 2.

Lemma: Let G be a planar graph. Consider a drawing of it. Let fi be the number of faces
with i edges. Then the following holds:

2|E| = 3f3 + 4f4 + 5f5 + ...

Proposition: K5 is not planar.

Note: |E| ≤ 3|V | − 6

Four Colour Theorem: The chromatic number of a planar graph is atmost 4.

Note: The proof of the above theorem is very non - elementary.

Six Colour Theorem: The chromatic number of a planar graph is atmost 6.

Platonic Solids: Platonic solids are three-dimensional shapes with identical, regular polygonal
faces, equal edges, and the same number of faces meeting at each vertex.

Proposition: There are 5 platonic solids: the tetrahedron (4 triangular faces), cube or hexa-
hedron (6 square faces), octahedron (8 triangular faces), dodecahedron (12 pentagonal faces),
and icosahedron (20 triangular faces).

6 Matchings in Bipartite Graphs

Matchings: Let G be a bipartite graph with sets A and B. A matching for the set A is a set
of edges {ab | a ∈ A, b ∈ B}, no two adjacent, such that every vertex a ∈ A is the endpoint of
one of them.

Perfect Matching: A matching is called perfect if all vertices are used, that is, if |A| = |B|.

Definition: For a vertex x, we denote by N (x) the set of its neighbours. For a set of ver-
tices X, we
S denote by N (X) the set of neighbours of atleast one vertex in X. In other words,
N (X) = x∈X N (x).

We also denote by NY (X) the set of neighbours of X in Y : NY (X) = N (X) ∩ Y

8
Hall’s Theorem: Consider a bipartite graph with sets A, B. If for every set X ∈ A, we
have |N (X)| ≥ |X|, then there is a matching for A.

Note: The condition |N (X)| ≥ |X| is called Hall’s condition.

Hall’s Marriage Theorem: Consider a group of n women and n men, where each woman
has a list of men she is willing to marry. There exists a way to marry all the women to distinct
men (such that no two women marry the same man) if and only if, for every subset of women,
the total number of men they collectively find acceptable is at least as large as the number of
women in that subset.

Corollary: Let G be a 2k−regular graph. Then G has a 2−regular spanning subgraph.

7 Extremal Graph Theory

Turan Graph: Let r ≥ 2 and n be positive integers. If we write n = cr + s, where 0 ≤ s < r
is the residue when n is divided by r, then the Turan graph Tr (n) is the complete r−partite
graph with s sets of c + 1 vertices and r − s sets of c vertices.

(r − 1)(n2 − s2 )
 
s
Proposition: The Turan graph has tr (n) = + edges.
2r 2
Turan’s Theorem: The maximal number of edges of a Kr+1 −free graph with n vertices
is tr (n), the number of edges of the Turan graph Tr (n)

(r − 1)(n2 )
Corollary: A Kr+1 −free graph on n vertices has atmost edges.
2r
√
n + n 4n − 3
Proposition: A graph on n ≥ 4 vertices with no 4-cycle has atmost edges.
4

8 Ramsey Theory
Ramsey’s Theorem: For any a and b positive integers, there exists a number N , such that
if n ≥ N , for any red-blue colouring of Kn , there exists either a red Ka subgraph or a blue Kb
subgraph. The least such N is denoted by R(a, b) and called a Ramsey number.

Bounds for Ramsey Numbers: The following are some useful bounds for ramsey numbers:
• Proposition: R(a, b) ≤ R(a − 1, b) + R(a, b − 1).
• Proposition: R(a, b) ≤a+b−2 Ca−1
• Proposition: R(a, b) > (a − 1)(b − 1)
• Proposition: R(a, a) ≥ 2a/2 ∀ a ≥ 3

Generalized Ramsey’s Theorem: For a1 , a2 , ..., ar positive integers, there exists a minimal
number R(a1 , a2 , ..., ar ) such that any colouring with r colours of the edges of a complete graph
on atleast R(a1 , a2 , ..., ar ) vertices yeilds a Kai subgraph with all edges of colour i, for some i.

Schur’s Theorem: For all r ∈ N there is a number N (r) with the following property: If
n ≥ N (r) and the integers in the set {1, 2, ..., n} are coloured with r colours, then there are
three elements x, y, z, not necessarily distinct, of the same colour such that: x + y = z.

9
9 Directed Graphs
Directed Graphs: A directed graph (or digraph) G(V, E) consists of a set V of vertices and
a set E of edges, which are ordered pairs (u, v) with u, v ∈ V , u ̸= v. An edge (u, v) is often
denoted by u → v or uv.
⃗

Degree: There are two main kinds of degrees: d+ (v) is the number of vertices u such that
v → u (the number of edges ’going out of v’, which is referred to as the outdegree), and d− (v)
is the number of vertices u such that u → v (the number of edges ’going into v’, the indegree.)
We can define d(v) = d+ (v) + d− (v).

Regular Digraphs: A directed graph is k - regular if for any v, d+ (v) = d− (v) = k (i.e.
from each vertex there are k edges going in and k edges going out).

Directed Path: A directed path from u to v is a sequence of vertices u = v1 , v2 , ..., vk = v

such that vi → vi+1 is a directed edge. A non - directed path is such a sequence in which vi vi+1
is an edge, but not necessarily directed towards vi+1 .

Note: The same definition may be extended to cycles and circuits.

Strongly Connected Digraphs: A directed graph is strongly connected if for any two ver-
tices v and u, there is a directed path from v to u.

Weakly Connected Digraphs: A directed graph is weakly connected if for any two ver-
tices u and v, there is a non - directed path from u to v.

Acyclic Digraphs: A directed graph is acyclic if it doesn’t contain any directed cycle.

Proposition: If G is a directed graph that is weakly connected but not strongly connected,
then the vertices can be partitioned into two non - empty sets A and B such that any edge
between A and B is directed towards B.

Proposition: Let G be a graph such that for every vertex v, d+ (v) = d− (v), then G is
weakly connected if and only if it is strongly connected.

Euler’s Theorem for Directed Graphs: Let G be a weakly connected directed graph.
Then G has an (directed) Eulerian circuit if and only if d+ (v) = d− (v) for all vertices v.

Arborescence: An arborescence is a directed graph such that the graph ignoring orienta-
tions is a tree, and when looking at orientations, there exists a vertex v, called the root, such
that there exists a directed path from v to all other vertices.

Proposition: In an arborescence, all vertices u which are not the root have d− (u) = 1. The
root v, has d− (v) = 0.

Theorem: There are nn−1 arborescences on n labelled vertices.

Cayley’s Theorem: There are nn−1 (undirected) trees on n labelled vertices.

Tournaments: A tournament is a directed graph in which between every two vertices there is
exactly one edge.

10
Transitive Tournaments: A transitive tournament is a tournament in which the vertices
can be labelled v1 , v2 , ..., vn such that vi → vj if and only if i < j.

Proposition: In any tournament there is a (directed) hamiltonian path, that is, a path con-
taining all vertices.

Camion’s Theorem: A tournament has a (directed) hamiltonian cycle if and only if it is

strongly connected.

Proposition: Let G be a tournament. Then either G contains a (directed) hamiltonian cycle

or its vertices can be partitioned into sets A and B such that all the edges between A and B
are from A to B.

Orienting Graphs: To orient the edges of non - directed graphs to be able to use the properties
of directed graphs is known as the technique of orientation.

10 Infinite Graphs
Infinite Graphs: An infinite graph is a graph in which the set of vertices (and possibly that
of edges) is infinite.

Countable Graphs: A countable graph is an infinite graph in which the set of vertices can
be indexed by natural numbers: V = {v1 , v2 , ...}.

Locally Finite Graphs: G is called locally finite if all of its vertices have finitely many
neighbours (i.e. finite degree).

Rays: A ray is a sequence of distinct vertices v1 , v2 , ... such that vi is connected with vi+1
for all i (i.e. an infinite path).

Double Rays: A double ray is a sequence of distinct vertices ..., v−1 , v0 , v1 , ... such that vi
is connected with all vi+1 (i.e. an ’infinite path extending in both directions’).

Hall’s Theorem for Countable Graphs: Let G be a locally finite countable bipartite graph
with sets A and B such that for any finite subset X of A, |N (X)| ≥ |X|. Then there exists a
matching for A.

Proposition: In a connected, locally finite countable graph, there is a path of length n for any
n.

Konig’s Infinity Lemma: Any connected locally finite graph contains a ray.

Ramsey Theory for Countable Graphs: Let n be a positive integer. The edges of a com-
plete countable graph are coloured with n colours. Then there exists an infinite monochromatic
complete subgraph.

11