GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

Abstract. Chapter 1 introduces some basic terminology. 1.1 is concerned with the existence and
construction of a graph with a given degree sequence. 1.2 presents some families of graphs to which
frequent reference occurs throughout the course. 1.4 introduces the notion of distance, which is fundamental to many applications. 1.5 introduces paths, trees, and cycles, which are critical concepts to
much of the theory.

Outline

1.1
1.2
1.4
1.5

Graphs and Digraphs

Common Families of Graphs
Walks and Distance
Paths, Cycles, and Trees

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

1.

Graphs and Digraphs

terminology for graphical objects

p

B
a
r

Figure 1.1: Simple graph A; graph B.

c
u

c
g

h
d

h
d

Figure 1.3: Digraph D; its underlying graph G.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

Degree
k
v
y

a b
z

d
w

Figure 1.9: A graph with degree sequence 6, 6, 4, 1, 1, 0.

Figure 1.10: Both degree sequences are h3, 3, 2, 2, 2, 2i.

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Proposition 1.1. A non-trivial simple graph G must have at least one

pair of vertices whose degrees are equal.
Proof. pigeonhole principle

Theorem 1.2 (Eulers Degree-Sum Thm). The sum of the degrees
of the vertices of a graph is twice the number of edges.
Corollary 1.3. In a graph, the number of vertices having odd degree is
an even number.
Corollary 1.4. The degree sequence of a graph is a finite, non-increasing
sequence of nonnegative integers whose sum is even.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

General Graph with Given Degree Sequence

v7
v6

v2

v5
v4

v3

v1

Figure 1.11: General graph with deg seq h5, 4, 3, 3, 2, 1, 0i.

Simple Graph with Given Degree Sequence

< 3, 3, 2, 2, 1, 1 >
Cor. 1.1.7
< 2, 1, 1, 1, 1 >
Cor. 1.1.7
< 0, 0, 1, 1 >
permute
< 1, 1, 0, 0 >
Cor. 1.1.7
< 0, 0, 0 >
Figure 1.13: Simple graph with deg seq h3, 3, 2, 2, 1, 1i.

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Havel-Hakimi Theorem
Theorem 1.6. Let hd1, d2, . . . , dni be a graphic sequence, with
d1 d2 . . . dn
Then there is a simple graph with vertex-set {v1, . . . , vn} s.t.
deg(vi) = di

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

with v1 adjacent to vertices v2, . . . , vd1+1.

Proof. Among all simple graphs with vertex-set
V = {v1, v2, . . . , vn} and deg(vi) = di : i = 1, 2, . . . , n
let G be a graph for which the number
r = |NG(v1) {v2, . . . , vd1+1}|
is maximum. If r = d1, then the conclusion follows.
Alternatively, if r < d1, then there is a vertex
vs : 2 s d1 + 1
such that v1 is not adjacent to vs, and vertex
vt : t > d 1 + 1
such that v1 is adjacent to vt (since deg(v1) = d1).

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

Moreover, since deg(vs) deg(vt), vertex vk such that vk is adj to vs

e be the graph obtained from
but not to vt, as on the left of Fig 1.14. Let G
G by replacing edges v1vt and vsvk with edges v1vs and vtvk , as on the right
of Fig 1.14, so all degrees are all preserved.
v1

v2 v 3

vs

v1

v d1 +1
vk

vt

v2 v 3

vs

v d1 +1

vt

vk

Figure 1.14: Switching adjacencies while preserving all degrees.

Thus, |NGe (v1) {v2, . . . , vd1+1}| = r + 1, which contradicts the choice of

graph G.

Corollary 1.7 (Havel (1955) and Hakimi (1961)). A sequence hd1, d2, . . . , dni
of nonneg ints, such that d1 d2 . . . dn, is graphic if and only if
the sequence


d2 1, . . . , dd1+1 1, dd1+2, . . . , dn
is graphic. (See Exercises for proof.)

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Remark 1.1. Cor 1.7 yields a recursive algorithm that decides whether a
non-increasing sequence is graphic.
Algorithm: Recursive GraphicSequence(hd1, d2, . . . , dni)
Input: a non-increasing sequence hd1, d2, . . . , dni.
Output: TRUE if the sequence is graphic; FALSE if it is not.
If d1 = 0
Return TRUE
Else
If dn < 0
Return FALSE
Else
Let ha1, a2, . . . , an1i be a non-incr permutation
of hd2 1, . . . , dd1+1 1, dd1+2, . . . , dni.
Return GraphicSequence(ha1, a2, . . . , an1i)

GRAPH THEORY LECTURE 1

2.

K1

K2

INTRODUCTION TO GRAPH MODELS

Families of Graphs

K3

K4

Figure 2.1: The first five complete graphs.

Figure 2.2: Two bipartite graphs.

Figure 2.4: The complete bipartite graph K3,4 .

K5

10

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Tetrahedron

Octahedron

Cube

Dodecahedron

Icosahedron

Figure 2.5: The five platonic graphs.

Figure 2.6: The Petersen graph.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

B2
B4

Figure 2.8: Bouquets B2 and B4 .

D4

Figure 2.9: The Dipoles D3 and D4 .

P2
P4
Figure 2.10: Path graphs P2 and P4 .

11

12

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

C1

C2

C4

Figure 2.11: Cycle graphs C1 , C2 , and C4 .

Figure 2.12: Circular ladder graph CL4 .

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

13

Circulant Graphs
Def 2.1. To the group of integers
Zn = {0, 1, . . . , n 1}
under addition modulo n and a set
S {1, . . . , n 1}
we associate the circulant graph
circ(n : S)
whose vertex set is Zn, such that two vertices i and j are adjacent if and
only if there is a number s S such that i + s = j mod n or j + s = i
mod n. In this regard, the elements of the set S are called connections.
circ(5 : 1, 2)

circ(6 : 1, 2)

circ(8 : 1, 4)
7

Figure 2.13: Three circulant graphs.

14

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Intersection and Interval Graphs

Def 2.2. A simple graph G with vertex set
VG = {v1, v2, . . . , vn}
is an intersection graph if there exists a family of sets
F = {S1, S2, . . . , Sn}
s. t. vertex vi is adjacent to vj if and only i 6= j and Si Sj 6= .
Def 2.3. A simple graph G is an interval graph if it is an intersection
graph corresponding to a family of intervals on the real line.
Example 2.1. The graph G in Figure 2.14 is an interval graph for the
following family of intervals:
a (1, 3)

b (2, 6)
d

a
1

b
2

c (5, 8)

d (4, 7)

c
5

Figure 2.14: An interval graph.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

15

Line Graphs
Line graphs are a special case of intersection graphs.
Def 2.4. The line graph L(G) of a graph G has a vertex for each edge
of G, and two vertices in L(G) are adjacent if and only if the corresponding
edges in G have a vertex in common.
Thus, the line graph L(G) is the intersection graph corresponding to the
endpoint sets of the edges of G.
Example 2.2. Figure 2.15 shows a graph G and its line graph L(G).
a

a
b
f

d
e

c
d

L(G)

Figure 2.15: A graph and its line graph.

16

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

4.

Walks and Distance

Def 4.1. A walk from v0 to vn is an alternating sequence

W = hv0, e1, v1, e2, ..., vn1, en, vni
of vertices and edges, such that
endpts(ei) = {vi1, vi},

for i = 1, ..., n

In a simple graph, there is only one edge beween two consecutive vertices of
a walk, so one could abbreviate the walk as
W = hv0, v1, . . . , vni
In a general graph, one might abbreviate as
W = hv0, e1, e2, ..., en, vni
Def 4.2. The length of a walk or directed walk is the number of edge-steps
in the walk sequence.
Def 4.3. A walk of length zero, i.e., with one vertex and no edges, is called
a trivial walk.
Def 4.4. A closed walk (or closed directed walk ) is a nontrivial walk
(or directed walk) that begins and ends at the same vertex. An open walk
(or open directed walk ) begins and ends at different vertices.
Def 4.5. The distance d(s, t) from a vertex s to a vertex t in a graph G
is the length of a shortest s-t walk if one exists; otherwise, d(s, t) = .

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

17

Eccentricity, Diameter, and Radius

Def 4.6. The eccentricity of a vertex v, denoted ecc(v), is the distance
from v to a vertex farthest from v. That is,
ecc(v) = max{d(v, x)}
xVG

Def 4.7. The diameter of a graph is the max of its eccentricities, or,
equivalently, the max distance between two vertices. i.e.,
diam(G) = max{ecc(x)} = max {d(x, y)}
xVG

x,yVG

Def 4.8. The radius of a graph G, denoted rad(G), is the min of the
vertex eccentricities. That is,
rad(G) = min {ecc(x)}
xVG

Def 4.9. A central vertex v of a graph G is a vertex with min eccentricity.

Thus, ecc(v) = rad(G).
Example 4.7. The graph of Fig 4.7 below has diameter 4, achieved by the
vertex pairs u, v and u, w. Vertices x and y have eccentricity 2 and all other
vertices have greater eccentricity. Thus, the graph has radius 2 and central
vertices x and y.
x

u
y

Figure 4.7: A graph with diameter 4 and radius 2.

18

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Connectedness
Def 4.10. Vertex v is reachable from vertex u if there is a walk from u
to v.
Def 4.11. A graph is connected if for every pair of vertices u and v, there
is a walk from u to v.
Def 4.12. A digraph is connected if its underlying graph is connected.
Example 4.8. The non-connected graph in Figure 4.8 is made up of connected pieces called components. See 2.3.
k
v
y

a b
z

d
w

Figure 4.8: Non-connected graph with three components.

GRAPH THEORY LECTURE 1

5.

INTRODUCTION TO GRAPH MODELS

19

Paths, Cycles, and Trees

Def 5.1. A trail is a walk with no repeated edges.

Def 5.2. A path is a trail with no repeated vertices (except possibly the
initial and final vertices).
Def 5.3. A walk, trail, or path is trivial if it has only one vertex and no
edges.
Example 5.1. In Fig 5.1, W = hv, a, e, f, a, d, zi is the edge sequence of a
walk but not a trail, because edge a is repeated, and T = hv, a, b, c, d, e, ui
is a trail but not a path, because vertex x is repeated.

u
f
v

e
a

z
c

W = <v, a, e, f, a, d, z>
T = <v, a, b, c, d, e, u>

y
Figure 5.1: Walk W is not a trail; trail T is not a path.

20

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Cycles
Def 5.4. A nontrivial closed path is called a cycle. It is called an odd
cycle or an even cycle, depending on the parity of its length.
Def 5.5. An acyclic graph is a graph that has no cycles.
Eulerian Graphs
Def 5.6. An eulerian trail in a graph is a trail that contains every edge
of that graph.
Def 5.7. An eulerian tour is a closed eulerian trail.
Def 5.8. An eulerian graph is a graph that has an eulerian tour.

c
d

k
f
e

Figure 5.6: An eulerian graph.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

21

Hamiltonian Graphs
Def 5.9. A cycle that includes every vertex of a graph is call a hamiltonian cycle.
Def 5.10. A hamiltonian graph is a graph that has a hamiltonian cycle.
(6.3 elaborates on hamiltonian graphs).

Figure 5.3: An hamiltonian graph.

22

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Girth
Def 5.11. The girth of a graph with at least one cycle is the length of a
shortest cycle. The girth of an acyclic graph is undefined.
Example 5.2. The girth of the graph in Figure 5.7 is 3 since there is a
3-cycle but no 2-cycle or 1-cycle.

Figure 5.7: A graph with girth 3.

GRAPH THEORY LECTURE 1

INTRODUCTION TO GRAPH MODELS

Trees
Def 5.12. A tree is a connected graph that has no cycles.

tree

non-tree
Figure 5.8: A tree and two non-trees.

non-tree

23

24

GRAPH THEORY LECTURE 1 INTRODUCTION TO GRAPH MODELS

Theorem 5.4. A graph G is bipartite iff it has no odd cycles.

Proof. Nec (): Suppose G is bipartite. Since traversing each edge in a
walk switches sides of the bipartition, it requires an even number of steps for
a walk to return to the side from which it started. Thus, a cycle must have
even length.
Suff (): Let G be a graph with n 2 vertices and no odd cycles. W.l.o.g.,
assume that G is connected. Pick any vertex u of G, and define a partition
(X, Y ) of V as follows:
X = {x | d(u, x) is even}; Y = {y | d(u, y) is odd}
Suppose two vertices v and w in one of the sets are joined by an edge e. Let
P1 be a shortest u-v path, and let P2 be a shortest u-w path. By definition
of the sets X and Y , the lengths of these paths are both even or both odd.
Starting from vertex u, let x be the last vertex common to both paths (see
Fig 5.9).
x
u

e
w

Figure 5.9: Figure for suff part of Thm 5.4 proof.

Since P1 and P2 are both shortest paths, their u x sections have equal
length. Thus, the lengths of the x v section of P1 and the x w section
of P2 are either both even or both odd. But then the concatenation of those
two sections with the edge e forms an odd cycle, contradicting the hypothesis.
Hence, (X, Y ) is a bipartition of G.


GRAPH THEORY LECTURE 1

7.

INTRODUCTION TO GRAPH MODELS

25

Supplementary Exercises

Exercise 1 A 20-vertex graph has 62 edges. Every vertex has degree 3

or 7. How many vertices have degree 3?
Exercise 8

How many edges are in the hypercube graph Q4?

Exercise 11 In the circulant graph circ(24 : 1, 5), what vertices are at

distance 2 from vertex 3?
Def 7.1. The edge-complement of a simple graph G is the simple graph
G on the same vertex set such that two vertices of G are adjacent if and only
if they are not adjacent in G.
Exercise 20 Let G be a simple bipartite graph with at least 5 vertices.
Prove that G is not bipartite. (See 2.4.)