Lecture 2, version April 6, 2023 page 1

Math 530 Spring 2022, Lecture 2: Degrees in

simple graphs
website: https://www.cip.ifi.lmu.de/~grinberg/t/22s

1. Simple graphs (cont’d)

1.1. Degrees
The degree of a vertex in a simple graph just counts how many edges contain
this vertex:

Definition 1.1.1. Let G = (V, E) be a simple graph. Let v ∈ V be a vertex.

Then, the degree of v (with respect to G) is defined to be

deg v := (the number of edges e ∈ E that contain v)

= (the number of neighbors of v)
= |{u ∈ V | uv ∈ E}|
= |{e ∈ E | v ∈ e}| .

(These equalities are pretty easy to check: Each edge e ∈ E that contains v
contains exactly one neighbor of v, and conversely, each neighbor of v belongs
to exactly one edge that contains v. However, these equalities are specific to
simple graphs, and won’t hold any more once we move on to multigraphs.)
For example, in the graph

3 2

4 1 5
,

the vertices have degrees

deg 1 = 3, deg 2 = 2, deg 3 = 3, deg 4 = 2, deg 5 = 0.

Here are some basic properties of degrees in simple graphs:

Proposition 1.1.2. Let G be a simple graph with n vertices. Let v be a vertex

of G. Then,
deg v ∈ {0, 1, . . . , n − 1} .
Lecture 2, version April 6, 2023 page 2

Proof. All neighbors of v belong to the (n − 1)-element set V ( G ) \ {v}. Thus,

their number is ≤ n − 1.

Proposition 1.1.3 (Euler 1736). Let G be a simple graph. Then, the sum of
the degrees of all vertices of G equals twice the number of edges of G. In
other words,
∑ deg v = 2 · |E (G)| .
v ∈V( G )

Proof. Write G as G = (V, E); thus, V ( G ) = V and E ( G ) = E.

Now, let N be the number of all pairs (v, e) ∈ V × E such that v ∈ e. We
compute N in two different ways (this is called “double-counting”):

1. We can obtain N by computing, for each v ∈ V, the number of all e ∈ E

that satisfy v ∈ e, and then summing these numbers over all v. Since these
numbers are just the degrees deg v, the result will be ∑ deg v.
v ∈V

2. On the other hand, we can obtain N by computing, for each e ∈ E, the

number of all v ∈ V that satisfy v ∈ e, and summing these numbers over
all e. Since each e ∈ E contains exactly 2 vertices v ∈ V, this result will be
∑ 2 = | E | · 2 = 2 · | E |.
e∈ E

Since these two results must be equal, we thus see that ∑ deg v = 2 · | E|.
v ∈V
But that’s the claim of Proposition 1.1.3.

Corollary 1.1.4 (handshake lemma). Let G be a simple graph. Then, the

number of vertices v of G whose degree deg v is odd is even.

Proof. Proposition 1.1.3 yields that ∑ deg v = 2 · |E ( G )|. Hence, ∑ deg v

v ∈V( G ) v ∈V( G )
is even. However, if a sum of integers is even, then it must have an even number
of odd addends. Thus, the sum ∑ deg v must have an even number of odd
v ∈V( G )
addends. In other words, the number of vertices v of G whose degree deg v is
odd is even.
Corollary 1.1.4 is often stated as follows: In a group of people, the number of
persons with an odd number of friends (in the group) is even. It is also known
as the handshake lemma.
Here is another property of degrees in a simple graph:

Proposition 1.1.5. Let G be a simple graph with at least two vertices. Then,
there exist two distinct vertices v and w of G that have the same degree.
Lecture 2, version April 6, 2023 page 3

Proof. Assume the contrary. So the degrees of all n vertices of G are distinct,
where n = |V ( G )|.
In other words, the map

deg : V ( G ) → {0, 1, . . . , n − 1} ,
v 7→ deg v

is injective. But this is a map between two finite sets of the same size (n). When
such a map is injective, it has to be bijective (by the pigeonhole principle).
Therefore, in particular, it takes both 0 and n − 1 as values.
In other words, there are a vertex u with degree 0 and a vertex v with degree
n − 1. Are these two vertices adjacent or not? Yes because of deg v = n − 1; no
because of deg u = 0. Contradiction!
(Fine print: The two vertices u and v must be distinct, since 0 ̸= n − 1. It is
here that we are using the “at least two vertices” assumption!)

Here is an application of counting neighbors to proving a fact about graphs.

This is known as Mantel’s theorem:

Theorem 1.1.6 (Mantel’s theorem). Let G be a simple graph with n vertices

and e edges. Assume that e > n2 /4. Then, G has a triangle (i.e., three distinct
vertices that are pairwise adjacent).

Example 1.1.7. Let G be the graph (V, E), where

V = {1, 2, 3, 4, 5, 6} ;
E = {12, 23, 34, 45, 56, 61, 14, 25, 36} .

Here is a drawing:
3 2

4 1

5 6
.
This graph has no triangle (which, by the way, is easy to verify without
checking all possibilities: just observe that every edge of G joins two vertices
of different parity, but a triangle would necessarily have two vertices of equal
parity). Thus, by the contrapositive of Mantel’s theorem, it satisfies e ≤ n2 /4
with n = 6 and e = 9. This is indeed true because 9 = 62 /4. But this also
entails that if we add any further edge to G, then we obtain a triangle.
Lecture 2, version April 6, 2023 page 4

Proof of Mantel’s theorem. We will prove the theorem by strong induction on n.

Thus, we assume (as the induction hypothesis) that the theorem holds for all
graphs with fewer than n vertices. We must now prove it for our graph G with
n vertices. Let V = V ( G ) and E = E ( G ), so that G = (V, E).
We must prove that G has a triangle. Assume the contrary. Thus, G has no
triangle.
From e > n2 /4 ≥ 0, we see that G has an edge. Pick any such edge, and call
it vw. Thus, v ̸= w.
Let us now color each edge of G with one of three colors, as follows:

• The edge vw is colored black.

• Each edge that contains exactly one of v and w is colored red.

• All other edges are colored blue.

The following picture shows an example of this coloring:

w 4

5
.

We now count the edges of each color:

• There is exactly 1 black edge – namely, vw.

• How many red edges can there be? I claim that there are at most n − 2.
Indeed, each vertex other than v and w is connected to at most one of v
and w by a red edge, since otherwise it would form a triangle with v and
w.

• How many blue edges can there be? The vertices other than v and w,
along with the blue edges that join them, form a graph with n − 2 vertices;
this graph has no triangles (since G has no triangles). By the induction
Lecture 2, version April 6, 2023 page 5

hypothesis, however, if this graph had more than (n − 2)2 /4 edges, then
it would have a triangle. Thus, it has ≤ (n − 2)2 /4 edges. In other words,
there are ≤ (n − 2)2 /4 blue edges.

In total, the number of edges is therefore

≤ 1 + (n − 2) + (n − 2)2 /4 = n2 /4.

In other words, e ≤ n2 /4. This contradicts e > n2 /4. This is the contradiction
we were looking for, so the induction is complete.
Quick question: What about equality? Can a graph with n vertices and
exactly n2 /4 edges have no triangles? Yes (for even n). Indeed, for any even n,
we can take the graph

({1, 2, . . . , n} , {ij | i ̸≡ j mod 2})

(keep in mind that ij means the 2-element set {i, j} here, not
the product i · j).
We can also do this for odd n, and obtain a graph with n2 − 1 /4 edges (which
is as close to n2 /4 as we can get when n is odd – after all, the number of edges
has to be an integer). So the bound in Mantel’s theorem is optimal (as far as
integers are concerned).

Mantel’s theorem can be generalized:

Theorem 1.1.8 (Turan’s theorem). Let r be a positive integer. Let G be a

simple graph with n vertices and e edges. Assume that

r − 1 n2
e> · .
r 2
Then, there exist r + 1 distinct vertices of G that are mutually adjacent.

Mantel’s theorem is the particular case for r = 2. We will see a proof of

Turan’s theorem later (Theorem 1.3.1 in Lecture 23).

1.2. Graph isomorphism

Two graphs can be distinct and yet “the same up to the names of their vertices”:
for instance,

1 2 3 1 3 2
and .

Let us formalize this:

Lecture 2, version April 6, 2023 page 6

Definition 1.2.1. Let G and H be two simple graphs.

(a) A graph isomorphism (or isomorphism) from G to H means a bijection

ϕ : V ( G ) → V ( H ) that “preserves edges”, i.e., that has the following
property: For any two vertices u and v of G, we have

(uv ∈ E ( G )) ⇐⇒ (ϕ (u) ϕ (v) ∈ E ( H )) .

(b) We say that G and H are isomorphic (this is written G ∼

= H) if there
exists a graph isomorphism from G to H.

Here are two examples:

• The two graphs

1 2 3 1 3 2
and

are isomorphic, because the bijection between their vertex sets that sends
1, 2, 3 to 1, 3, 2 is an isomorphism. Another isomorphism between the
same two graphs sends 1, 2, 3 to 2, 3, 1.

• The two graphs

3 2

1 2 3
4 1

5 6 A B C
and

are isomorphic, because the bijection between their vertex sets that sends
1, 2, 3, 4, 5, 6 to 1, B, 3, A, 2, C is an isomorphism.

Here are some basic properties of isomorphisms (the proofs are straightfor-
ward):

Proposition 1.2.2. Let G and H be two graphs. The inverse of a graph iso-
morphism ϕ from G to H is a graph isomorphism from H to G.
Lecture 2, version April 6, 2023 page 7

Proposition 1.2.3. Let G, H and I be three graphs. If ϕ is a graph isomor-

phism from G to H, and ψ is a graph isomorphism from H to I, then ψ ◦ ϕ is
a graph isomorphism from G to I.

As a consequence of these two propositions, it is easy to see that the relation

∼
= (on the class of all graphs) is an equivalence relation.
Graph isomorphisms preserve all “intrinsic” properties of a graph. For ex-
ample:

Proposition 1.2.4. Let G and H be two simple graphs, and ϕ a graph isomor-
phism from G to H. Then:

(a) For every v ∈ V ( G ), we have degG v = deg H (ϕ (v)). Here, degG v

means the degree of v as a vertex of G, whereas deg H (ϕ (v)) means the
degree of ϕ (v) as a vertex of H.

(b) We have |E ( H )| = |E ( G )|.

(c) We have |V ( H )| = |V ( G )|.

One use of graph isomorphisms is to relabel the vertices of a graph. For

example, we can relabel the vertices of an n-vertex graph as 1, 2, . . . , n, or as
any other n distinct objects:

Proposition 1.2.5. Let G be a simple graph. Let S be a finite set such that
|S| = |V ( G )|. Then, there exists a simple graph H that is isomorphic to G
and has vertex set V ( H ) = S.

Proof. Straightforward.