November 14, 2017
5 – Graph Theory Basics
William T. Trotter
[email protected]
Basic Definitions
Definition A graph G is a pair (V, E) where V is a
finite set and E is a set of 2-element subsets of
V. The set V is called the vertex set of G and the
set E is called the edge set of G.
Example G = (V, E) where V = {1, 2, A, x, B, a} and
E = { {1, A}, {2, x}, {x, a}, {A, B}, {B, 2}, {2, a}}.
Its All About Adjacency
Comment We show below two drawings of the same graph
whose vertex set is {1, 2, 3, 4, 5, 6}.
Its All About Adjacency (2)
Comment We show below two drawings of graphs, each
having vertex set {1, 2, 3, 4, 5, 6}, but now they represent
different graphs.
Its All About Adjacency (3)
Question Is this a drawing of one graph whose vertex set
is {1, 2, 3, …, 12} or do we have drawings of two graphs,
one with vertex set {1, 2, 3, 4, 5, 6} and the other {7, 8,
9, 10, 11, 12}?
Answer Depends on the meaning of V in the pair (V, E).
Notation and Terminology
1. Vertices are also called nodes, points, locations,
stations, etc.
2. Edges are also called arcs, lines, links, pipes,
connectors, etc.
3. Remember that mathematicians are selectively
lazy so when there is no confusion, an edge {x, y}
will be denoted as xy. This can create some
confusion when vertices are positive integers as
how would one interpret a comment such as
“consider the edge 2786”.
Notation and Terminology (2)
1. When xy is an edge in G, we say x and y are
adjacent in G. Alternatively, we say they are
neighbors in G.
2. In a graph G, the set of all neighbors of a vertex
x is denoted NG(x). And when the graph G is
fixed in the discussion, this is typically
abbreviated to just N(x).
3. The integer |NG(x)| is called the degree of x in
G, and is denoted degG(x). Again, when the graph
is fixed, this is shortened to deg(x).
Notation and Terminology (3)
Example A graph with vertex set {1, 2, 3, …, 12}.
Questions Are 8 and 11 neighbors? What is
deg(8)?
First Theorem in Graph Theory
Example Let G = (V, E) be a graph and let q be the
number of edges in G. Then σ𝑥 ∊𝑉 𝑑𝑒𝑔𝐺 𝑥 = 2𝑞
Exercise Verify this theorem for the graph
illustrated above.
Carlos and Dave
Overheard in Conversation Dave said that he was
working with a graph and carefully counted all the
degrees and said here is full listing of all the values:
16, 13, 12, 18, 16, 22, 11, 16, 14, 10, 8, 12, 14, 16, 8, 7,
10, 20, 12, 14, 16, 8, 6, 6, 8, 4, 8, 6, 6, 6, 6, 8, 10, 5, 8,
8, 6, 6, 6, 6, 3, 6, 4, 8, 8, 8, 4, 8, 10, 12
Carlos remarked gently “Perhaps you should check
your work.”
The Notion of a Subgraph
Definition A graph G’ = (V’, E’) is a subgraph of a
graph G = (V, E) when V’ is contained in V and E’
is contained in E.
Example On the left, we show a graph with vertex
set {1, 2, …, 8}. The graph on the right is a subgraph.
The Notion of a Subgraph
Question We show a graph G with vertex set {1, 2,
…, 8} on the left. Is the graph on the right a
subgraph?
Paths in Graphs
Definition Let G = (V, E) be a graph. When n ≥ 1, a
sequence P = (x1, x2, …, xn) of n distinct vertices in
G is called a path from x1 to xn in G if xi is
adjacent to xi+1 in G whenever 1 ≤ i < n.
Example In the graph shown, (7, 9, 8, 5, 2, 6, 4) is a
path from 7 to 4.
Size of Paths
Convention Many authors measure how big a path is
in terms of the number of edges, so they will say that
a path (a, b, c, d, e) from a to e has length 4. In
particular, they would say that when x and y are
neighbors, the path (x, y) has length 1. Other
authors prefer to measure paths in terms of the
number of vertices, so they would say that the path
(a, b, c, d, e) has size 5. We prefer the second
option, so we will always talk about paths of a certain
size and this will count the number of vertices and not
the number of edges.
Connected Graphs
Definition Let G = (V, E) be a graph. We say G is
connected if for all x, y in V with x ≠ y, there is a
path from x to y in G.
Example The graph shown below is connected.
Connected Graphs (2)
Definition Let G = (V, E) be a disconnected graph. A
subgraph H = (V’, E’) of G is called a component of G if
H is connected and any subgraph of G which contains H
properly is disconnected. Is this graph connected? If
not, how many components does it have?
Cycles in Graphs
Definition Let G = (V, E) be a graph. When n ≥ 3, a
sequence P = (x1, x2, …, xn) of n distinct vertices in
G is called a cycle of size n in G if xi is adjacent to
xi+1 in G whenever 1 ≤ i < n and xn is adjacent to x1
in G.
Example In the graph shown, (5, 8, 9, 7, 1, 3) is a
cycle of size 6.
Loose Points in Graphs
Definition A vertex x in a graph G is called a loose
point (also an isolated point) if it has no neighbors, i.e.,
degG(x) = 0.
Example Below we show a graph with vertex set {1, 2, …,
11}. In this graph, vertices 2 and 4 are loose points.
Cliques in Graphs
Definition Let G = (V, E) be a graph. When n ≥ 1,
a set S of vertices in G is called a clique if any
two distinct vertices in S are adjacent in G.
Example In this graph, the subsets {2}, {6, 10},
{1, 3, 5} and {5, 8, 9, 10, 11} are cliques. There
are many more.
Xing and Zori
Overheard in Conversations Xing is a very good
programmer and remarked to Zori that he could easily
detect whether a large graph was connected and if it
was disconnected whether it had any loose vertices.
Zori was not impressed as she couldn’t see any reason
why anybody would care about either issue. Still,
moderately annoyed with Xing’s enthusiasm, she asked
him about a problem she had read about on the web:
Could he tell whether a graph on 2n vertices had a
clique of size n. Xing hadn’t thought about it … but
now that he was challenged, he said he thought he
could. Hmmm …
Questions for Thought
Challenges or Not? Given a graph G = (V, E) with
|V| = n, which of the following problems is easy and which
is hard?
1. Is G connected?
2. Does G have a path of size at least n/2?
3. Does G have a cycle of size at least n/2?
4. Does G have a clique of size at least n/2?
Also Suppose Alice and Bob are arguing about the
correct answers to these questions for a graph with
n = 10,000. Would you rather defend a ‘’yes” answer or a
‘’no’’ answer.
Isomorphic Graphs
Definition Graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic when there is a bijection f: V1 V2 so
that {x, y} is an edge in G1 if and only if {f(x), f(y) }
is an edge in G2.
Exercise Show that the two graphs shown below are
isomorphic.
Another Question for Thought
Challenge or Not? Given two graphs G1 = (V1, E1) and
G2 = (V2, E2), is it hard to tell whether they are
isomorphic? If Yolanda says “yes” and Bob says “no”,
who has the easier task to convince an impartial
referee?
Induced Subgraphs
Definition A graph H = (V’, E’) is an induced
subgraph of a graph G = (V, E) if V’ V and xy
is an edge in H whenever x and y are distinct
vertices in V’ and xy is an edge in G. In the
drawing below, the graph on the right is an induced
subgraph of the graph on the left.
Induced Subgraphs (2)
Remark When G = (V, E) is a graph, an induced
subgraph of G is determined entirely by its vertex
set, so for example, the induced subgraph on the
right can be denoted as G – {6, 7}.
Cut Vertices
Definition A vertex x in a graph G is called a cut
vertex of G if the induced subgraph G – x has
more components than G. In the graph shown
below, 4 and 7 are cut vertices.
Special Classes of Graphs
Definition For n ≥ 3, Cn denotes a cycle on n
vertices. Here are C3, C4, C5 and C6.
C3 C4
C5 C6
Special Classes of Graphs (2)
Definition For n ≥ 1, Kn denotes a complete graph
(also called a clique) on n vertices. Here are K1,
K2, K3, K4, K5 and K6.
K1 K2 K3 K4 K5 K6
Special Classes of Graphs (3)
Definition A graph G on n vertices is a tree if G
is connected and contains no cycles.
Properties of Trees
Definition When T is a tree, a vertex of degree 1
is called a leaf. This tree has five leaves: 3, 6, 7, 8,
10. The other vertices are cut vertices.
Properties of Trees (2)
Theorem When T is a tree on n vertices and
n ≥ 2, then T has at least two leaves.
Proof Induction on n. Obviously true when n = 2.
Assume valid when T is a tree with at least 2 and
at most k vertices for some k ≥ 2. Then let T
be a tree with k + 1 vertices. Then k + 1 ≥ 3, so
if T does not have 3 leaves, it has a cut vertex
x. It follows that if C is a component of G –x,
then C + x is a tree and has at least 2 leaves.
One of these is distinct from x and is therefore
a leaf in T.
Properties of Trees (3)
Theorem When T is a tree on n vertices, T
has n – 1 edges.
Proof Induction on n. True when n = 1. Now
assume valid when n = k for some integer k ≥ 1.
Then let T be a tree on k + 1 vertices. Choose a
leaf x (there are at least two from which to
choose). Then deg(x) = 1 while the tree T – x
has k vertices and k – 1 edges. Therefore T
has (k – 1) + 1 = k edges.
Paths and Trees
Theorem When T is a tree, T is a path unless
it has more than two leaves.
Counting Trees
Exercise Explain why there are 6 unlabelled trees
on 6 vertices. They are shown below.
The Unlabelled Trees on 6 Vertices
Exercise Show that when 1 ≤ n ≤ 6, the number of
trees with vertex set {1, 2, …, n} is nn-2. Actually,
we did the work when 1 ≤ n ≤ 5 in class, so all you
really have to do is the case n = 6.
Remark Later in the course, we will show that this
is true for all n ≥ 1.
