1. What is a graph?

Contents
a. What is a Graph? a. Testing for Planarity
b. Definitions and Examples b. Thickness
2. Eulerian Graphs c. Duality
a. Eulerian Trails and Circuits 7. Coloring Graphs
a. Dominant Sets, independence and Cliques
b. Postman Problems
b. Vertex coloring, edge coloring
3. Hamiltonian Graphs c. Chromatic polynomial
a. Elementary Existence Theorems d. Coloring Maps
b. The Traveling Salesperson Problem e. 4-color theorem, 5-color theorem
4. Path Algorithms 8. Connectivity
a. Edge Connectivity
a. The shortest Path Algorithms
b. Vertex Connectivity
b. The Longest Path Algorithms c. Menger’s Theorems and Connectivity
c. Transitive Closure Algorithm 9. Networks and Flows
d. Biconnectivity a. Networks and Flows
e. Depth-Fist Search b. Maximum flow Problem
c. Multi-Commodity Flow Problem
f. Breadth-First Search
d. Minimum Cost Flow Algorithm
5. Trees e. Circulation Problem
a. Spanning Trees 10. Matchings
b. Centers and Bicenters a. Definitions
c. Binary Trees b. Maximum Matchings
c. Maximum Weight Matchings
d. Counting Trees
d. factor
e. Searching Trees 11. Graph and Np-Completeness
6. Planar Graph a. NP-Completeness
a. Euler’s Formula b. NP-Complete Problems in Graph 4

b. Genus
 What is a Graph?
 A set of Objects
 Relations between pairs of Objects
 A Graph G=(V,E)

 A set V of Vertices/Nodes

 A set E of Edges

5
 Vocabulary

 We can name individual vertices and edges

 e Connects u and v

 u and v are End Points of e

 u and e are Incident

 u and v are Adjacent

 u and v are Neighbors

6
How about drawing these shapes?

7
The Königsberg Bridge problem

 Problem: Find a route crossing each bridge exactly once and

returning to the starting point.

 Leonard Euler(1707-1783) proved that it is impossible.

8
 Abstract connection

Abstract
land

9
 History of Graph Theory

The paper written by Leonhard Euler on the Seven Bridges of

Königsberg and published in 1736 is regarded as the first paper in
the history of graph theory.

More than one century after Euler's paper on the bridges of

Königsberg and while Listing introduced topology, Cayley was led
by the study of particular analytical forms arising from differential
calculus to study a particular class of graphs, the trees. This study
had many implications in theoretical chemistry.

The term "graph" was introduced by Sylvester in a paper published

in 1878 in Nature. 10
 Definitions and Examples

Definitions: Two or more edges joining the same pair of vertices are
called multiple edges and an edge joining a vertex to itself is called a
loop. A graph with no loops or multiple edges is called a simple graph.

11
Definition: A subgraph of a graph G is a graph whose vertex set is a
subset of that of G, and whose adjacency relation is a subset of that of
G restricted to this subset. In the other direction, a supergraph of a
graph G is a graph of which G is a subgraph.

2 2
4 4
1 1
3 3

G A subgraph of G

Definition: The degree of a vertex v, written d(v), is the number of

edges incident with v.

(ex)
2
deg(1)=2, deg(2)=4,
4 deg(3)=4, deg(4)=2
1
3
12
G
A regular graph is a graph where each vertex has the same number of
neighbors, i.e. every vertex has the same degree or valency.
A regular graph with vertices of degree k is called a k-regular graph or
regular graph of degree k.

2 3 2 2
2
4
1 1 1
3 3 3 1
3

0-regular 1-regular 2-regular 3-regular

13
 Walk
A walk is an alternating sequence of vertices and edges, beginning and
ending with a vertex, where each vertex is incident to both the edge
that precedes it and the edge that follows it in the sequence, and where
the vertices that precede and follow an edge are the end vertices of that
edge.
A walk is closed if its first and last vertices are the same, and open if
they are different.
The length l of a walk is the number of edges that it uses. For an open
walk, l = n–1, where n is the number of vertices visited (a vertex is
counted each time it is visited). For a closed walk, l = n
w z
(u,v,w,x,v,w,x,y,z,x): open walk, length=9
u v x y

w
v x
(u,v,w,x,y,w,x,y,u): closed walk, length=8
u 14
y
 Trail, Path, Circuit, Cycle
Definition: If all the edges (but not necessarily all the vertices) of a
walk are different, then the walk is called a trail. If, in addition, all the
vertices are different, then the trails is called a path.

w z
(u,v,w,x,y,z,x): trail
u v x y (u,v,w,x,y,z) : path (simple path)

A closed walk in which no edges repeat is a circuit.

(v,w,x,y,z,x,v)

 cycle (simple circuit) is a circuit with no repeated vertices (except start

and end).
15
(x,y,z,x): cycle of length 3. (v,w,x,y,z,x,v) is not a cycle.
 Connected Graph
A Graph G is connected if there is a path in G between any given pair
of vertices, and disconnected otherwise. Every disconnected graph can
be split up into a number of connected subgraphs, called components.

A connected graph has only one component.

1
3

A disconnected graph A connected graph

16
 Handshaking Lemma
Handshaking Lemma: Every finite undirected graph has an even
number of vertices with odd degree.
In more colloquial terms, in a party of people some of whom shake
hands, an even number of people must have shaken an odd number of
other people's hands.
In any graph, the sum of all the vertex-degrees is equal to twice the
number of edges.
 [proof]
Since each edge has two ends, it must contribute exactly 2 to the sum
of the degrees. The result follows immediately.
 It is a consequence of the degree sum formula (also sometimes called
the handshaking lemma).
 deg( v)  2 E
vV
17
 (ex)

In this graph, an even number of vertices (the

four vertices numbered 2, 4, 5, and 6) have
odd degrees. The sum of the degrees of the
vertices is 2 + 3 + 2 + 3 + 3 + 1 = 14, twice
the number of edges.

 Consequences of the Handshaking Lemma

1. In any graph, the sum of all the vertex-degrees is an even number.
2. In any graph, the number of vertices of odd degree is even.
3. If G is a graph which has n vertices and is regular of degree r,
then G has exactly nr/2 edges.

18
 Practice
 Problem 1
 Determine the number of edges in a graph having
 6 Vertices
 2 having degree of 4
 4 having degree of 2
 Draw a graph for the information above with the number of edges det
ermined using handshaking lemma.
 Problem 2
 A graph contains 21 edges and 3 vertices of degree 4, and all the othe
r vertices of degree 2. Find total number of vertices.
 Problem 3
 A simple graph G has 24 edges and degree of each vertex is 4. Find th
e number of vertices.
 Problem 4
 A graph has 24 edges and degree of each vertex is k, then which of th
e following is possible no of vertices 19
 20 - 15 -10 - 8
 Isomorphic Graphs
1 2 3 1 b 3

?
=
a b c a 2 c

G H

 G is very similar to H, but, they are not the same graph.

 We express this similarity by saying the graphs represented by theses
two diagrams are isomorphic.
 We can relabel the vertices in G to get H.
 identical behavior
 One to one correspondence between vertices, edges and incidence
relationship is preserved
20
 If there is a bijection
 Isomorphic Graphs
Bijection
 A bijection, or a bijective function, is a function f from a set X to a set
Y with the property that, for every y in Y, there is exactly one x in X
such that f(x) = y and no unmapped element exists in either X or Y.
 Alternatively, f is bijective if it is a one-to-one correspondence
between those sets; i.e., both one-to-one (injective) and onto
(surjective).-전단사함수

A bijective function, f, where set X is {1,2,3,4}

and set Y is {D,B,C,A}. For example, f(1)=D.

21
 An injective function (not a bijection): 단사함수
 if x1, x2∈X with f(x1) = f(x2) then x1 = x2

A non-injective function
(this one happens to be a surjection(onto)

 surjective(전사함수):
if y ∈Y, then there exists at least one x∈X such
that f(x) = y.

function f is a relation that satisfies

1. for all x ∈X, there exists y ∈ Y, f(x)=y
2. for all x ∈X, y,z ∈Y, if f(x)=y, f(x)=z, then y=z.
22
 Isomorphic Graphs
An isomorphism of graphs G and H is a bijection between the vertex
sets of G and H
f: V(G) →V(H)
such that any two vertices u and v of G are adjacent in G if and only if
ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly
called "edge-preserving bijection", in accordance with the general
notion of isomorphism being a structure-preserving bijection.
Two graphs G and H are isomorphic if H can be obtained from G by
relabeling the vertices – that is, if there is a one-to-one correspondence
between the vertices of G and those of H, such that the number of
edges joining any pair of vertices in G is equal to the number of edges
joining the corresponding pair of vertices in H.
23
Examples of Isomorphic Graphs

ƒ(a) = 1, ƒ(b) = 6
ƒ(c) = 8, ƒ(d) = 3
ƒ(g) = 5, ƒ(h) = 2
G ƒ(i) = 4, ƒ(j) = 7 H

24
 Practice
Problem 1
 How many simple non isomorphic graphs are possible with 3 vertices.
Problem 2
 How many simple non isomorphic graphs are possible with 4 vertices and
2 edges.
Determine whether these graphs are isomorphic

Problem 3

Problem 4
25
 Directed Graphs (Digraphs)
Definition: An ordered pair G = (V, A) with V a set whose elements are
called vertices or nodes, and A a set of ordered pairs of vertices, called
arcs, directed edges, or arrows. 1

2 3

An arc a = (x, y) is considered to be directed from x to y; y is called the

head and x is called the tail of the arc; y is said to be a direct successor
of x, and x is said to be a direct predecessor of y.

x y

If a path leads from x to y, then y is said to be a successor of x and

reachable from x, and x is said to be a predecessor of y. The arc (y, x) is
called the arc (x, y) inverted.
26
x u v y
Definition: Two or more arcs joining the same pair of vertices in the
same directions are called multiple arcs, and an arc joining a vertex to
itself is called a loop. A Digraph with no loops or multiple arcs is
called a simple digraph.
1 4

2 3

Definition: Let D be a directed graph. The underlying graph of D is the

graph obtained by replacing each arc of D by the corresponding
(undirected) edge.
1 4 1 4

2 3 2 3 27
Underlying graph
Let D be a digraph with vertex-set V(D) and arc-list A(D). A
subdigraph of D is a digraph all of whose vertices belong to V(D) and
all of whose arcs belong to A(D).
1 4 1 4 4

2 3 2 3 2 3
D
subdigraphs

Two digraphs C and D are isomorphic if D can be obtained from C by

relabeling the vertices – that is, if there is a one-to-one correspondence
between the vertices of C and those of D, such that the number of arcs
joining any pair of vertices in C is equal to the number of arcs joining
the corresponding pair of vertices (in the same direction) in D.
u v 1 2

4
C and D are isomorphic.
z w 3
C D
28
 Definitions: A digraph D is connected if its underlying graph is a
connected graph, and disconnected otherwise. If it is strongly connected
if there is a path in D from any vertex to any other.

(ex)
1 5 1 5 1 5

2 3 7 3 7 2 3 6 7
6 2 6
4 8 4 8 4 8
A B C
 Digraph A is disconnected since its underlying graph is a disconnected
graph.
 Digraph B is connected but not strongly connected since there is no path
from 6 to 3.
 Digraph C is strongly connected since there are paths joining all pairs of
vertices.
29
 Definition: A graph D is orientable if it is the underyling graph of a
strongly connected digraph – that is, if it is possible to ‘direct’ the edges
of G in such a way that the resulting digraph is strongly connected.
(Ex)

A B
 In (A) , we see that the edges of the complete graph K5 can be
‘directed’ in such a way that the resulting digraph is strongly
connected →orientable.
 But, (B) can not be. – a bridge exists.

 Definition: An edge in a connected graph is a bridge if its removal leaves

a disconnected graph.
30
Theorem: A connected graph G is orientable if and only if it has no
bridges.

A directed graph G is called symmetric if, for every arc that belongs to
G, the corresponding inverted arc also belongs to G. A symmetric
loopless directed graph is equivalent to an undirected graph with the
pairs of inverted arcs replaced with edges; thus the number of edges is
equal to the number of arcs halved.

1 1

=
2 3 2 3

31
 Definition: Let D be a digraph and let v be a vertex of D. The out-
degree of v is the number of arcs incident from v, and is denoted by
outdeg(v). Similarly, The in-degree of v is the number of arcs incident
to v, and is denoted by indeg(v).
1

 outdeg(1)=1, indeg(3)=2 3 G
2
4

 The Handshaking Di-Lemma. In any digraph, the sum of all the out-
degrees and the sum of all the in-degrees are each equal to the number
of arcs.
 In G, sum of out-degrees = 1+2+1+1=5, sum of in-degrees =
1+1+2+1=5, the number of arcs=5.

32
 Summary
Covered the vocabulary and definitions of basic concepts of graphs
Discussed handshaking theorem and isomorphic graphs
Understood directed graphs and its concepts

33
 Thanks
Next Lecture:
Graph Basics - II

34