GRAPH THEORY LECTURE NOTES 3

1. Basics of Graphs
The graph are mathematical structures used to e!ectively model pairwise relations between
objects. We will use the following standard notations throughout the text.

1.1. Definition: Formally, we define a graph to be an ordered pair G = (V, E) where E →

[V ]2 := {Y → V : |Y | = 2} or ! "
A graph, G is an ordered pair (V, E), where V is a finite set and E → V2 is a set of pairs of
elements in V .
• G = (V, E) is an arbitrary (undirected, simple) graph
• |V | is its number of vertices
• |E| is its number of edges
Example 1.1. In this example V = {1, 2, 3, 4, 5, 6, 7}, with edge set
E = {{1, 2}, {1, 5}, {2, 5}, {3, 4}, {5, 7}} .

Example 1.2. Another example, where vertices are shown as A, B, C and D and edges
labelled as e1 := (A, B), e2 := (A, C)e3 := (B, D), e4 := (C, D), e5 := (C, D).
e1
A B

e5
e2 e3

C D
e4

1.2. Notations and Terminologies: For a graph G, the set V (G) is the vertex set of G
and E(G) is the edge set.
• The order of G is |V (G)|, often written |G|.
• The size of G is |E(G)|, often written ||G||.
• Self loop An edge that is associated with same vertex as both its end vertices is called
self loop. or, having an edge with both ends at the same vertex. Such edges are called
loop or self loop.
4 ARUN MAITI

e1
e8 A B
e6

e5
e2 e3

C e4 D e9
e7

Fig. 1.1. graph with parallel edges and loops

• Parallel edges The edges associated with same pair of start & end vertices are called
parallel edges, or having more than one edge between the same two vertices. Such
edges are called parallel edges.
• Simple graph A graph that has neither self loop nor parallel edges is called a simple
graph. The examples of graph above in Fig 1.1 and 1.2 are clearly simple graphs.
• We shall not always distinguish strictly between a graph and its vertex or edge set.
For example, we may speak of a vertex v ↑ G (rather than v ↑ V (G)), an edge e ↑ G,
and so on.
• A vertex v is incident with an edge e if v ↑ e; then e is an edge at v. The set of all
incidents edges to a vertex v is denoted by |E(v)|. The degree of a vertex v is defined
to be |E(v)|.
• Two vertices x, y of G are adjacent, or neighbours, if x, y is an edge of G.
• A pendant vertex is a vertex whose degree is 1.
• An edge that has a pendant vertex as an end vertex is a pendant edge.
• An isolated vertex is a vertex whose degree is 0.
• A graph with no edges is called Null Graph.
• The degree of a vertex is sometimes also known as valency.
• Two graphs G, H are said to be isomorphic if there exists a bijection f : V (G) ↓ V (H)
such that (u, v) ↑ E(G) ↔↗ (f (u), f (v)) ↑ E(H).
• A subgraph of G is another graph H with V (H) → V (G), E(H) → E(G).
• A simple graph that contains every possible edge between all the vertices is called a
complete graph. The complete graph with ! "n vertices is denoted by Kn .
• A complete graph with n vertices is ([n], n2 ). Every graph of order ↘ n is a subgraph
of Kn . The following graphs are complete graphs:

K3 K4

• The minimum degree of the vertices in a graph G is denoted ω(G) (which equals 0 if
there is an isolated vertex in G). Similarly, we write !(G) as the maximum degree
of vertices in G.
 GRAPH THEORY LECTURE NOTES 5

• The complement or inverse of a graph G is a graph H on the same vertices such that
two distinct vertices of H are adjacent if and only if they are not adjacent in G. That
is, to generate the complement of a graph, one fills in all the missing edges required
to form a complete graph, and removes all the edges that were previously there.

• A graph with infinite number of vertices is an example of Infinite graph. For example:

v1 ↓ v2 ↓ v3 ↓ v4 ↓ · · ·

Remark 1.3. In this course, we only consider finite graphs, i.e. V and E are finite sets.
We shall not always distinguish strictly between a graph and its vertex or edge set. For
example, we may speak of a vertex v ↑ G (rather than v ↑ V (G)), an edge e ↑ G, and so on.

1.3. Subgraphs. A subgraph G→ of a graph G is a graph G→ whose vertex set and edge set
are subsets of those of G. If G→ is a subgraph of G, then G is said to be a supergraph of G→ .
An induced subgraph of a graph is another graph, formed from a subset of the vertices of
the graph and all of the edges, from the original graph, connecting pairs of vertices in that
subset.

1.4. Graph operations. Let G1 = (V1 , E1 ) and G2 = (V2 , E2 ) be the following graphs.
Then

• G1 ≃ G2 = (V1 ≃ V2 , E1 ≃ E2 )
• G1 ⇐ G2 = (V1 ⇐ V2 , E1 ⇐ E2 )
• G1 ⇒ G2 = (V1 \ V2 , E1 \ E2 )

Given two graph G and G→ shown below, the union, di!erence and intersection G≃G→ , G⇐G→ ,
respectively of these graphs as shown below:
6 ARUN MAITI

Definition 1.4. A graph G is said to have been decomposed into two subgraphs H1 and H2
if
H1 ≃ H2 = G and H1 ⇐ H2 = a null graph.
i.e.,
• Every edge of G occurs in either H1 or H2 but not in both.
• Some vertices, however, may occur in both H1 and H2 .
Definition 1.5. Deletion of Vertex and Edge, and Fusion in Graph
Vertex Deletion
Let G = (V, E) be a graph with vertex set V and edge set E. For a vertex v ↑ V , the deletion
of v from G results in a subgraph G→ defined as follows:
G→ = G ⇒ v = (V → , E → )
where V → = V \ {v} and E → = {e ↑ E | v ↑
/ e}. This means that G→ is obtained by removing
v and all edges incident to v.
Edge Deletion
Let G = (V, E) be a graph with vertex set V and edge set E. For an edge e = {u, v} ↑ E,
the deletion of e from G results in a subgraph G→ defined as follows:
G→ = G ⇒ e = (V, E → )
where E → = E \ {e}. This means that G→ is obtained by removing e but keeping all vertices of
G.

Example 1.6. Illustration of the above process:

 GRAPH THEORY LECTURE NOTES 7

v1

e1
G G ⇒ v1 G ⇒ e1

Fig. 1.2. Examples of vertex and edge deletion in a graph.

Fusion in Graph
Let G = (V, E) be a graph with vertex set V and edge set E. Fusion of two vertices u, v ↑ V
(also known as vertex contraction) results in a graph G→ defined as follows:
• Replace vertices u and v with a single new vertex w.
• Replace all edges {u, x} and {v, x} with edges {w, x}, removing any duplicate edges
(if G is a simple graph).
• Remove any self-loops formed during this process.
• The number of vertices will always be reduced by one in fusion operation, one cannot
say the same about edges.
Formally, the new graph G→ = (V → , E → ) is defined as:
V → = (V \ {u, v}) ≃ {w}

E → = {{w, x} | {u, x} ↑ E or {v, x} ↑ E, x ⇑= u, x ⇑= v}

Example 1.7. Example of Fusion:

v1 v2

G1 Fusion of v1 and v2 G→

Fig. 1.3. Fusion of vertices v1 and v2 in a graph.

1.5. Walks, Paths, and Cycles. A walk in a graph G = (V, E) is a finite sequence of
vertices and edges, v0 , e1 , v1 , e2 , . . . , ek , vk , such that ei = (vi↑1 , vi ) for i = 1, 2, . . . , k. The
number k is the length of the walk. A walk is closed if v0 = vk and open otherwise.
A trail is a walk in which all edges are distinct.

A path is a walk in which all vertices (and thus all edges) are distinct.

A cycle is a trail in which only the first and last vertices are equal.
8 ARUN MAITI

Example. Consider the following graph G = (V, E):

In this graph:
• v1 , e1 , v2 , e2 , v3 , e3 , v4 is a walk of length 3.
• v1 , e1 , v2 , e2 , v3 , e5 , v1 is a closed walk of length 3.
• v1 , e1 , v2 , e2 , v3 , e3 , v4 is a path of length 3.
• v1 , e1 , v2 , e2 , v3 , e3 , v4 , e4 , v1 is a cycle of length 4.
v1

g a

v3 b v2

d e f

v4 h v5
In above graph,
• Example of an open walk: v1 ↓ v2 ↓ v4 ↓ v3 ↓ v2
• Example of a closed walk: v1 ↓ v2 ↓ v4 ↓ v5 ↓ v2 ↓ v1
• Example of a trail: v1 ↓ v2 ↓ v4 ↓ v5 ↓ v2
• Example of a path: v1 ↓ v2 ↓ v4 ↓ v5
• Example of a cycle: v2 ↓ v4 ↓ v5 ↓ v2

1.6. Connected Graphs. A graph is connected if there is a u ⇒ v path (a path from u to

v in G for every pair u, v ↑ V (G).

• A null graph of more than 1-vertex is a disconnected graph.

• The components of G are the maximal connected subgraphs of G (induced by the
equivalence classes of the relation u ⇓ v ↔↗ u = v or there is a u ⇒ v path).
Example 1.8. The following graph has 4 components.

Theorem 1.9. A graph G is disconnected if and only if its vertex set V can be partitioned
into two nonempty disjoint subsets V1 and V2 such that there exists no edge in G whose one
end vertex is in V1 and the other in V2 .
Proof:
(↗) Suppose G is disconnected. Then there exist two nonempty disjoint subsets V1 and
V2 of V such that there is no edge between any vertex in V1 and any vertex in V2 .
 GRAPH THEORY LECTURE NOTES 9

This follows directly from the definition of a disconnected graph, where there exist at
least two components with no edges connecting them.
(↔) Conversely, suppose V can be partitioned into two nonempty disjoint subsets V1 and
V2 such that there is no edge between V1 and V2 . Then there are no paths connecting
vertices in V1 to vertices in V2 . Therefore, G is disconnected.
1.7. The degree of a vertex.
Lemma 1.10. (Euler’s handshaking lemma). The sum of the degrees of the vertices of
a graph is equal to twice the number of edges. Or we say the graph G = (V, E), where
V = {v1 , . . . , vn } and E = {e1 , . . . , em }, satisfies
n
#
d(vi ) = 2m.
i=1
$
Proof. Each edge of G contributes 2 to the total degree count ni=1
$nd(vi ), one for each incident
vertices.
$ Therefore, m edges of G contributes 2m to the sum $i=1 d(vi ). Since each count
of ni=1 d(vi ) must be coming from one of the edges of G, hence ni=1 d(vi ) = 2m. ↭
Theorem 1.11. The number of vertices of odd degree in a graph is always even.
Proof. Let G be a graph with vertices v1 , v2 , · · · , vn and m edges. Then by the Handshake
lemma,
n
#
d(vi ) = 2m
i=1
# #
=↗ d(vi ) + d(vi ) = 2m
d(vi ) is odd d(vi ) is even
# #
=↗ d(vi ) = 2m ⇒ d(vi )
d(vi ) is odd d(vi ) is even
RHS is an even number because it is the sum of even numbers. Therefore, the LHS is an
even number. Hence proved.
Theorem 1.12. If a graph has exactly two vertices of odd degree, there must be a path joining
these two vertices.
Proof: Consider a graph G with exactly two vertices u and v of odd degree. If there is no
path between u and v, then u and v lie in two di!erent connected components of G.
In any connected component, the sum of the degrees of all vertices is even, since it is twice
the number of edges (each edge contributes 2 to the sum of degrees).
However, if u and v are in di!erent components, then each component has an odd sum of
degrees (since each has one vertex of odd degree). This contradicts the fact that the sum of
the degrees of vertices in any graph is always even. Thus, there must be a path joining u
and v.