Graphs

Agenda –Graphs
Graph basics and definitions
◦ Vertices/nodes, edges, adjacency, incidence
◦ Degree, in-degree, out-degree
◦ Degree, in-degree, out-degree
◦ Subgraphs, unions, isomorphism
◦ Adjacency matrices
Types of Graphs
◦ Trees
◦ Undirected graphs
◦ Simple graphs, Multigraphs, Pseudographs
◦ Digraphs, Directed multigraph
◦ Bipartite
◦ Complete graphs, cycles, wheels, cubes, complete bipartite
Uses of Graph Theory in CS
 Car navigation system
 Efficient database
 Build a bot to retrieve info off WWW
 Representing computational models
 Many other applications.
Graphs –Intuitive Notion
 A graph is a bunch of vertices (or nodes) represented by
circles which are connected by edges, represented by line
segments.

 Mathematically, graphs are binary-relations on their

vertex set (except for multigraphs).
 In Data Structures one often starts with trees and
generalizes to graphs. In this course, opposite approach:
We start with graphs and restrict to get trees.
 Trees
A very important type of graph in CS is called a tree:

Real
Tree
 Trees
A very important type of graph in CS is called a tree:

Real
transformation
Tree
 Trees
A very important type of graph in CS is called a tree:

Real
transformation
Tree
 Trees
A very important type of graph in CS is called a tree:

Real Abstract
transformation
Tree Tree
Simple Graphs
 Different purposes require different types of graphs.
 EG: Suppose a local computer network
 Is bidirectional (undirected)
 Has no loops (no “self-communication”)
 Has unique connections between computers
 Sensible to represent as follows:
Simple Graphs
{1,2}
1 2
{1,3} {2,3} {2,4}
{3,4}
3 4
{1,4}

Vertices are labeled to associate with particular computers

Each edge can be viewed as the set of its two endpoints
Simple Graphs
 DEF: A simple graph G = (V,E ) consists of a non-
empty set V of vertices (or nodes) and a set E (possibly
empty) of edges where each edge is a subset of V with
cardinality 2 (an unordered pair).
 Q: For a set V with n elements, how many possible
edges there?
Multigraphs
 If computers are connected via internet instead of
directly, there may be several routes to choose from for
each connection.
 Depending on traffic, one route could be better than
another.
 Makes sense to allow multiple edges, but still no self-
loops:
Multigraphs
e1
1 e2 2
e3 e4 e5
3 e6 4

Edge-labels distinguish between edges sharing same

endpoints. Labeling can be thought of as function:
e1  {1,2}, e2  {1,2}, e3  {1,3}, e4  {2,3}, e5  {2,3}, e6
 {1,2}
Multigraphs
DEF: A multigraph G = (V,E,f ) consists of a non-empty
set V of vertices (or nodes), a set E (possibly empty) of
edges and a function f with domain E and codomain the
set of pairs in V.
Pseudographs
If self-loops are allowed we get a pseudograph:
e1 e6
1 e2 2
e3 e4 e5 e7
3 4
Now edges may be associated with a single vertex, when the
edge is a loop
e1  {1,2}, e2  {1,2}, e3  {1,3},
e4  {2,3}, e5  {2}, e6  {2}, e7  {4}
Multigraphs
DEF: A pseudograph G = (V,E,f ) consists of a non-empty
set V of vertices (or nodes), a set E (possibly empty) of
edges and a function f with domain E and codomain the
set of pairs and singletons in V.
Undirected Graphs
Terminology
Vertices are adjacent if they are the endpoints of the same
edge.

e1
1 e2 2
e3 e4 e5
3 e6 4

Q: Which vertices are adjacent to 1? How about adjacent

to 2, 3, and 4?
Undirected Graphs
Terminology
e1
1 e2 2
e3 e4 e5
3 e6 4
A: 1 is adjacent to 2 and 3
2 is adjacent to 1 and 3
3 is adjacent to 1 and 2
4 is not adjacent to any vertex
Undirected Graphs
Terminology
A vertex is incident with an edge (and the edge is incident
with the vertex) if it is the endpoint of the edge.

e1
1 e2 2
e3 e4 e5
3 e6 4

Q: Which edges are incident to 1? How about incident to 2,

3, and 4?
Undirected Graphs
Terminology
e1
1 e2 2
e3 e4 e5
3 e6 4

A: e1, e2, e3, e6 are incident with 2

2 is incident with e1, e2, e4, e5, e6
3 is incident with e3, e4, e5
4 is not incident with any edge
Digraphs
Digraphs could be considered as a way of representing
relations:

1 3

Q: What type of pair should each edge be (multiple

edges not allowed)?
Digraphs
A: Each edge is directed so an ordered pair (or tuple) rather
than unordered pair.
(2,2)
2
(1,2) (2,3)
(1,1) 1 (1,3) 3 (3,3)
(2,4) (3,4)

4
(4,4)

Thus the set of edges E is just the represented relation on V.

Digraphs
 DEF: A directed graph (or digraph) G = (V,E )
consists of a non-empty set V of vertices (or nodes)
and a set E of edges with E V V.
 The edge (a,b) is also denoted by a b and a is called
the source of the edge while b is called the target of
the edge.
 Q: For a set V with n elements, how many possible
digraphs are there?
Directed Multigraphs
If also want to allow multiple edges in a digraph, get a
directed multigraph (or multi-digraph).

1 3

Q: How to use sets and functions to deal with multiple

directed edges, loops?
Directed Multigraphs
A: Have function with domain the edge set and codomain V
V .
e3
2
e1 e4 e6
e2 e5
1 3
e7

e1(1,2), e2(1,2), e3(2,2), e4  (2,3),

e5  (2,3), e6  (3,3), e7  (3,3)
Degree
The degree of a vertex counts the number of edges that
seem to be sticking out if you looked under a magnifying
glass:

e1 e6
1 e2 2 e5
e3 e4
3
Degree
The degree of a vertex counts the number of edges that
seem to be sticking out if you looked under a magnifying
glass:

e1 e6
1 e2 2 e5 magnify
e3 e4
3
Degree
The degree of a vertex counts the number of edges that
seem to be sticking out if you looked under a magnifying
glass:

e1 e6
1 e2 2 e5 magnify
e3 e4
3
Thus deg(2) = 7 even though 2 only incident with 5 edges.
Q: How to define this formally?
Degree
A: Add 1 for every regular edge incident with vertex
and 2 for every loop. Thus deg(2) = 1 + 1 + 1 + 2 + 2 = 7

e1 e6
1 e2 2 e5 magnify
e3 e4
3
Oriented Degree
when Edges are Directed
The in-degree of a vertex (deg-) counts the number of
edges that stick in to the vertex. The out-degree (deg+)
counts the number sticking out.

1 3

Q: What are in-degrees and out-degrees of all the

vertices?
Oriented Degree
when Edges are Directed
A: deg-(1) = 0
deg-(2) = 3
deg-(3) = 4 2
deg+(1) = 2
deg+(2) = 3 1 3

deg+(3) = 2
Handshaking Theorem
e1 e6
1 e2 2
e3 e4 e5 e7
3 4
There are two ways to count the number of edges in the
above graph:
1. Just count the set of edges: 7
2. Count seeming edges vertex by vertex and divide by 2
because double-counted edges:
( deg(1)+deg(2)+deg(3)+deg(4) )/2 = (3+7+2+2)/2 = 14/2 = 7
Handshaking Theorem
THM: In an undirected graph
1
| E |   deg( e)
2 eE
In a directed graph

|E|   deg
eE

(e)   deg
eE

(e)
Q: In a party of 5 people can each person be friends with
exactly three others?
Handshaking Theorem
A: Imagine a simple graph with 5 people as vertices and
edges being undirected edges between friends (simple
graph assuming friendship is symmetric and irreflexive).
Number of friends each person has is the degree of the
person.
Handshaking would imply that
|E | = (sum of degrees)/2 or
2|E | = (sum of degrees) = (5·3) = 15.
Impossible as 15 is not even.
Handshaking Theorem
Lemma: The number of vertices of odd degree must be
even in an undirected graph.
Proof :
Otherwise would have 2|E | = Sum of even no.’s
+ an odd number of odd no.’s
even = even + odd
–this is impossible.
Graph Patterns
Complete Graphs - Kn
A simple graph is complete if every pair of distinct
vertices share an edge. The notation Kn denotes the
complete graph on n vertices.

K1 K2 K3 K4 K5
Graph Patterns
Cycles - Cn
The cycle graph Cn is a circular graph with V = {0,1,2,…,n-
1} where vertex i is connected to i +1 mod n and to i -1
mod n. They look like polygons:

C1 C2 C3 C4 C5

Q: What type of graph are C1and C2 ?

Graph Patterns
Wheels - Wn
A: Pseudographs
The wheel graph Wn is just a cycle graph with an extra
vertex in the middle:

W1 W2 W3 W4 W5

Usually consider wheels with 3 or more spokes only.

Graph Patterns
Cubes - Qn
The n-cube Qn is defined recursively. Q0 is just a vertex. Qn+1
is gotten by taking 2 copies of Qn and joining each vertex v of
Qn with its copy v’ :

Q0 Q1 Q2 Q3 Q4 (hypercube)
Bipartite Graphs
A simple graph is bipartite if V can be partitioned into V
= V1 V2 so that any two adjacent vertices are in
different parts of the partition. Another way of
expressing the same idea is bichromatic : vertices can
be colored using two colors so that no two vertices of the
same color are adjacent.
Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Bipartite Graphs
EG: C4 is a bichromatic:

And so is bipartite, if we redraw it:

Q: For which n is Cn bipartite?

Bipartite Graphs
A: Cn is bipartite when n is even. For even n color all odd
numbers red and all even numbers green so that vertices
are only adjacent to opposite color.
If n is odd, Cn is not bipartite. If it were, color 0 red. So 1
must be green, and 2 must be red. This way, all even
numbers must be red, including vertex n-1. But n-1
connects to 0.
Graph Patterns
Complete Bipartite - Km,n
When all possible edges exist in a simple bipartite graph
with m red vertices and n green vertices, the graph is called
complete bipartite and the notation Km,n is used. EG:

K2,3 K4,5
Subgraphs
Notice that the 2-cube occurs

inside the 3-cube .

In other words, Q2 is a subgraph of Q3 :

DEF: Let G = (V,E ) and H = (W,F ) be graphs. H is said to
be a subgraph of G, if W  V and F  E.
Q: How many Q2 subgraphs does Q3 have?
Subgraphs
A: Each face of Q3 is a Q2 subgraph so the answer is 6, as
this is the number of faces on a 3-cube:
Unions
In previous example can actually reconstruct the 3-cube
from its 6 2-cube faces:
Unions
If we assign the 2-cube faces (aka Squares) the names S1, S2, S3,
S4, S5, S6 then Q3 is the union of its faces:

Q3 = S1S2S3S4S5S6
Unions
DEF: Let G1 = (V1, E1 ) and G2 = (V2, E2 ) be two simple
graphs (and V1,V2 may or may not be disjoint). The union
of G1, G2 is formed by taking the union of the vertices and
edges. I.E: G1G2 = (V1V2, E1E2 ).
A similar definitions can be created for unions of
digraphs, multigraphs, pseudographs, etc.
Adjacency Matrix
We already saw a way of representing relations on a set
with a Boolean matrix:
R digraph(R) MR

2 1 1 1 1
 
1 1 0 1 1 1
2 2 1 3 0 0 1 1
3 3  
0 1
4 4 4  0 0
Adjacency Matrix
Since digraphs are relations on their vertex sets, can
adopt the concept to represent digraphs. In the context
of graphs, we call the representation an adjacency
matrix :
For a digraph G = (V,E ) define matrix AG by:
Rows, Columns –one for each vertex in V
Value at i th row and j th column is
◦ 1 if i th vertex connects to j th vertex (i  j )
◦ 0 otherwise
Adjacency Matrix
-Directed Multigraphs
 Can easily generalize to directed multigraphs by
putting in the number of edges between vertices,
instead of only allowing 0 and 1:
 For a directed multigraph G = (V,E ) define the matrix
AG by:
 Rows, Columns –one for each vertex in V
 Value at i th row and j th column is
◦ The number of edges with source the i th vertex and target the
j th vertex
Adjacency Matrix
-Directed Multigraphs
Q: What is the adjacency matrix?

1 4 3
Adjacency Matrix
-Directed Multigraphs
2

A: 1 4 3

0 3 0 1
 
0 1 2 0
0 1 2 0
 
0 0 
 0 0
 Adjacency Matrix
-General
Undirected graphs can be viewed as directed graphs by
turning each undirected edge into two oppositely
oriented directed edges, except when the edge is a self-
loop in which case only 1 directed edge is introduced.

1 2 1 2

3 4 3 4
Adjacency Matrix
-General
Q: What’s the adjacency matrix?

1 2

3 4
Adjacency Matrix
-General
1 2

A:
3 4

0 2 1 0
 
2 2 1 0
Notice that answer is symmetric. 1 1 0 0
 
0 1 
 0 0
Adjacency Matrix
-General
 For an undirected graph G = (V,E ) define the matrix AG
by:
 Rows, Columns –one for each element of V
 Value at i th row and j th column is the number of edges
incident with vertices i and j.
 This is equivalent to converting first to a directed
graph as above. Or by allowing undirected edges to
take us from i to j can simply use definition for
directed graphs.
Graph Representation: Adjacency List
 Adjacency list. Node indexed array of lists.
Two representations of each edge. degree = number of neighbors of u

Space proportional to m + n.
Checking if (u, v) is an edge takes O(deg(u)) time.
Identifying all edges takes (m+n) time = linear time
for G(V,E).
Requires O(m+n) space. Good for dealing with sparse
graphs. 1 2 3

2 1 3 4 5

3 1 2 5 7 8

4 2 5

5 2 3 4 6

6 5

7 3 8

8 3 7
Graph Isomorphism
 Various mathematical notions come with their own
concept of equivalence, as opposed to equality:
 Equivalence for sets is bijectivity:
 EG { , , }  {12, 23, 43}

 Equivalence for graphs is isomorphism:

 EG


Graph Isomorphism
Intuitively, two graphs are isomorphic if can bend, stretch
and reposition vertices of the first graph, until the second
graph is formed. Etymologically, isomorphic means “same
shape”.
EG: Can twist or relabel:

to obtain:
Graph Isomorphism
Undirected Graphs
DEF: Suppose G1 = (V1, E1 ) and G2 = (V2, E2 ) are
pseudographs. Let f :V1V2 be a function s.t.:
1) f is bijective
2) for all vertices u,v in V1, the number of edges
between u and v in G1 is the same as the number of
edges between f (u) and f (v ) in G2.
Then f is called an isomorphism and G1 is said to be
isomorphic to G2.
Graph Isomorphism
Digraphs
DEF: Suppose G1 = (V1, E1 ) and G2 = (V2, E2 ) are directed
multigraphs. Let f :V1V2 be a function s.t.:
1) f is bijective
2) for all vertices u,v in V1, the number of edges from u
to v in G1 is the same as the number of edges between
f (u) and f (v ) in G2.
Then f is called an isomorphism and G1 is said to be
isomorphic to G2.
Note: Only difference between two definitions is the
italicized “from” in no. 2 (was “between”).
Graph Isomorphism
-Example
EG: Prove that

is isomorphic to .

First label the vertices:2 2

1 3 1 3
5 4
5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star.

2 2
1 3 1 3
5 4
5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3.

2 2
1 3 1 3
5 4
5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5.

2 2
1 3 1 3
5 4
5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2

2 2
1 3 1 3
5
4 5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2,
f (5) = 4.

2 2
1 3 1 3

5 4 5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2, f
(5) = 4. If we would continue, we would get back to f (1)
=1 so this process is well defined and f is a morphism.

2 2
1 3 1 3
5 4
5 4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2,
f (5) = 4. If we would continue, we would get back to f (1)
=1 so this process is well defined and f is a morphism.
Finally since f is bijective, f is an isomorphism.

2 2
1 3 1 3
5 4
5 4
Properties of Isomorphims
Since graphs are completely defined by their vertex sets
and the number of edges between each pair, isomorphic
graphs must have the same intrinsic properties. I.e.
isomorphic graphs have the same:
 number of vertices and edges
 degrees at corresponding vertices
 types of possible subgraphs
 any other property defined in terms of the basic graph
theoretic building blocks!
A property preserved by isomorphism of graphs is called
a graph invariant.
Graph Isomorphism
-Negative Examples
Once you see that graphs are isomorphic, easy to prove it.
Proving the opposite, is usually more difficult. To show
that two graphs are non-isomorphic need to show that
no function can exist that satisfies defining properties of
isomorphism. In practice, you try to find some intrinsic
property that differs between the 2 graphs in question.
Graph Isomorphism
-Negative Examples
A: Why are the following non-isomorphic?

u2 v2
u1 u3 v1 v3

u5 u4 v4
Graph Isomorphism
-Negative Examples
A: 1st graph has more vertices than 2nd.
Q: Why are the following non-isomorphic?

u2 v2
u1 u3 v1 v3

u5 u4 v5 v4
Graph Isomorphism
-Negative Examples
A: 1st graph has more edges than 2nd.
Q: Why are the following non-isomorphic?

u2 v2
u1 u3 v1 v3

u5 u4 v5 v4
Application
 Graph isomorphisms, and functions that are almost graph
isomorphisms, arise in applications of graph theory to chemistry
and to the design of electronic circuits, and other areas including
bioinformatics and computer vision.
 Because of the complexity of modern chips, automation tools are
used to design them. Graph isomorphism is the basis for the
verification that a particular layout of a circuit produced by an
automated tool corresponds to the original schematic of the
design.
 Graph isomorphism can also be used to determine whether a chip
from one vendor includes intellectual property from a different
vendor.
In-class Exercise
Show that W6 is not bipartite.