Fundamental Definitions and Basic Properties of Graphs

Starting from the formal definitions of undirected and directed graphs, we develop the notions of degree, the handshaking lemma, complete graphs $K_n$, complete bipartite graphs $K_{m,n}$, and graph isomorphism, with full proofs throughout.

Folio Official

March 1, 2026

1 What Is a Graph?

Definition 1 (Undirected graph).

An undirected graph is a pair

G = (V, E)

consisting of a nonempty finite set

V

and a set

E \subseteq (2 V)

whose elements are unordered pairs

{u, v}

with

u \neq = v

. The elements of

V

are called vertices and the elements of

E

are called edges. For an edge

e = {u, v} \in E

, we say that

u

and

v

are the endpoints of

e

, and that

u

and

v

are adjacent.

Definition 2 (Directed graph).

A directed graph (or digraph) is a pair

D = (V, A)

consisting of a nonempty finite set

V

and a subset

A \subseteq V \times V

(whether loops

(v, v)

are permitted depends on the context). The elements

(u, v) \in A

are called arcs;

u

is the tail and

v

is the head of the arc.

Definition 3 (Multigraphs and simple graphs).

A graph that allows multiple edges between the same pair of vertices is called a multigraph. A graph with no self-loops

{v, v}

and no multiple edges is called a simple graph. Unless stated otherwise, all graphs in this series are assumed to be simple and undirected.

Throughout, we write $V (G)$ and $E (G)$ for the vertex and edge sets of $G$ , and set $∣ V (G) ∣ = n$ and $∣ E (G) ∣ = m$ .

2 Degree and the Handshaking Lemma

Definition 4 (Degree).

For a vertex

v \in V (G)

, the degree of

v

, denoted

de g (v)

d (v)

, is the number of edges incident to

v

de g (v) = ∣ {e \in E (G) ∣ v \in e} ∣.

The minimum degree of

G

is written

δ (G)

and the maximum degree is written

Δ (G)

Theorem 5 (Handshaking lemma).

For any graph

G = (V, E)

v \in V \sum de g (v) = 2∣ E ∣.

Proof.

Each edge

e = {u, v}

contributes exactly

1

de g (u)

and

1

de g (v)

. Hence every edge is counted exactly twice in the sum on the left-hand side. □

Remark 6.

The name "handshaking lemma" comes from the interpretation: at a party, the total number of handshakes counted by all participants is always even. An immediate corollary is that every graph has an even number of vertices of odd degree.

Example 7.

Consider a graph on

5

vertices with degree sequence

(2, 3, 3, 2, 4)

. Then

\sum de g (v) = 14

, so the number of edges is

m = 7

. On the other hand, the sequence

(1, 2, 3, 3, 4)

has

\sum = 13

, which is odd; therefore no graph with this degree sequence can exist.

3 Complete Graphs and Complete Bipartite Graphs

Definition 8 (Complete graph).

A graph in which every pair of distinct vertices is joined by an edge is called a complete graph. The complete graph on

n

vertices is denoted

K_{n}

. It has

(2 n) = \frac{n ( n - 1 )}{2}

edges, and every vertex has degree

n - 1

Definition 9 (Bipartite graph and complete bipartite graph).

A graph

G

is bipartite if its vertex set admits a partition

V (G) = X ⊔ Y

(

X \cap Y = \emptyset

) such that every edge of

G

joins a vertex in

X

to a vertex in

Y

. If, moreover, every vertex in

X

is adjacent to every vertex in

Y

, then

G

is called a complete bipartite graph. When

∣ X ∣ = m

and

∣ Y ∣ = n

, we write

K_{m, n}

. The number of edges of

K_{m, n}

mn

The complete graph $K_{4}$ :

The complete bipartite graph $K_{2, 3}$ :

4 Complement of a Graph

Definition 10 (Complement).

For a simple graph

G = (V, E)

, the complement of

G

is the graph

\overline{G} = (V, (2 V) ∖ E)

. In other words,

{u, v} \in E (\overline{G}) ⟺ {u, v} \in / E (G)

Theorem 11.

For any simple graph

G

n

vertices,

∣ E (G) ∣ + ∣ E (\overline{G}) ∣ = (2 n)

Proof.

E (G)

and

E (\overline{G})

form a partition of

(2 V)

, so the result is immediate. □

5 Graph Isomorphism

Definition 12 (Graph isomorphism).

Two graphs

G_{1} = (V_{1}, E_{1})

and

G_{2} = (V_{2}, E_{2})

are isomorphic if there exists a bijection

φ : V_{1} \to V_{2}

such that

{u, v} \in E_{1} ⟺ {φ (u), φ (v)} \in E_{2} .

We then write

G_{1} ≅ G_{2}

Remark 13.

Graph isomorphism is an equivalence relation (it is reflexive, symmetric, and transitive). In graph theory, isomorphic graphs are usually regarded as "the same." To show that two graphs are not isomorphic, it suffices to find an invariant— such as the number of vertices, the number of edges, or the degree sequence — that differs between them. However, agreement of all known invariants does not guarantee isomorphism. The graph isomorphism problem lies in

NP

, but whether it is

NP

-complete remains an open question.

Example 14.

A graph on

5

vertices with

5

edges and degree sequence

(2, 2, 2, 2, 2)

is isomorphic to the

5

-cycle

C_{5}

. This is an instance where the vertex count and degree sequence alone determine the isomorphism class. In contrast, the degree sequence

(2, 2, 2, 2, 2, 2)

6

vertices is shared by both

C_{6}

and the disjoint union

C_{3} ⊔ C_{3}

, which are not isomorphic.

Graph Theory Discrete Mathematics Textbook Graph Definitions Degree Handshaking Lemma

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

Fundamental Definitions and Basic Properties of Graphs

1 What Is a Graph?

2 Degree and the Handshaking Lemma

3 Complete Graphs and Complete Bipartite Graphs

4 Complement of a Graph

5 Graph Isomorphism

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry