Concept of Graphs

Discrete Math 2
 Content
• Graph definition
• Terms on undirected graphs
• Terms on directed graphs
• Some special types of graphs
– Planar graph
– Bipartite graph
• Exercises

2
Graph definition
 Simple Undirected graph
• The simple undirected graph G= < V, E>, V is the set of vertices, E is
the unordered set of two different elements of V called edges.

4
 Undirected multigraph
• The undirected multigraph G = <V, E> consists of V as the set of vertices, E as
the family of unordered pairs of two different elements of V called the set of
edges.
• e1  E, e2  E are said to be multiple edges (cạnh bội) if they correspond to
a pair of vertices.

5
 Undirected pseudograph
• The undirected pseudograph G = <V, E> includes V as the set of vertices, E
as the family of unordered pairs of two elements (two elements are not
necessarily different) in V called edges.
• Edge e is called edge ring (loop) if there is the form e(u, u), where u is
some vertex in V .

6
 Directed Graph (Digraph)
• The directed graph G = <V, E> includes V as a set of vertices, E is a set of
ordered pairs (x,y) of two elements of V called e(x,y) or arcs.

7
 Directed multigraph
• The directed multigraph G = <V, E>, where V is the set of vertices, E is the
set of the ordered pairs (x,y) of two elements of V called egde(x,y) or arcs
(arcs can be looped, i.e multiple directed edges from a vertex to a second
(possibly the same) vertex).
• Two arcs e1, e2 corresponding to the same pair of vertices are called
multiple edges (cung lặp).

8
Different types of graphs

9
 Convention
• We mainly work with undirected and directed graphs.
• When writing "undirected graph" we understand as "simple
undirected graph".
• When writing "directed graph" we understand as "simple
directed graph".

10
Basic terms on undirected graphs
 Degree of the vertex
• Definition 1. Two vertices u and v of an undirected graph G =<V, E> are said to be
adjacent if (u,v) is an edge in the graph G.
– If e =(u, v) is an edge of a graph G, then we say that this edge incident with (belongs to) two
vertices u and v, or we say that the edge e connects vertex u to v. Vertices u and v are endpoints of
an edge e.
• Definition 2. We call the degree of vertex v in an undirected graph the number of
edges associated (incident) with it and denoted by deg(v).

12
 Ex

• deg(a) = 2, deg(b) =deg(c) = deg(f) = 4;

• deg(e) = 3, deg(d) = 1, deg(g)=0.
• Vertex with degree 0 is called an isolated vertex (g).
• Vertex with degree 1 are called (hanging) pendant vertex (d).
13
 Sum of degrees of vertices
THE HANDSHAKING THEOREM
Theorem 1. Let G = (V, E) be an undirected graph with m edges. Then
(Note that this applies even if multiple edges and loops are present.)

EXAMPLE: How many edges are there in a graph with 10 vertices each of degree six?

Solution: Because the sum of the degrees of the vertices is 6 ⋅ 10 = 60, it follows that 2m = 60
where m is the number of edges. Therefore, m = 30.

14
 Sum of degrees of vertices
THE HANDSHAKING THEOREM
Theorem 2. In an undirected graph G=<V, E>, the number of odd degree
vertices is an even number (ie. An undirected graph has an even number of vertices of
odd degree)

15
 Path, circuit (cycle)
Definition 1. Path of length n from vertex u to vertex v on an undirected graph
G=<V,E> is sequence x 0, x 1,..., x n-1, x n, where n is the number positive integer, x0=u,
xn=v, (xi , xi+1 )  E, i=0,1,2,...,n-1.

• This path can also be represented as a sequence of edges (x0, x1), (x1,x2),...,(xn-1, xn).
• The vertex u is the initial vertex and v the terminal vertex of the path.
• A cycle is the path that begins and ends at the same vertex.
• A path or cycle is said to be simple if no multiple edges.

16
 Example
• a, d, c, f, e are simple paths of length 4.
• d, e, c, a are not paths because (e,c) is not an edge of the graph.
• The sequence b, c, f, e, b is a cycle of length 4.
• The path a, b, e, d, a, b of length 5 is not a simple path because edge (a,b)
is present twice.

17
 Connected Graph
Definition 2. An undirected graph is said to be connected if it can always
find a path between any two of its vertices.
• In the case that the graph G=<V, E> is not connected, we can decompose
G into a number of connected subgraphs that have no common vertex.
– Each such subgraph is called a connected component of G.
– Thus, a graph is connected if and only if its number of connected
components is 1.
• For an undirected graph, if there exists a vertex u  V such that u has a
path to all the remaining vertices of the graph, we can conclude that the
graph is connected.

18
 Example
• The number of connected components of G is 3.

19
 cut edge (bridge), cut vertex
(cạnh cầu, đỉnh trụ (khớp)
Definition 3.
– Edge e  E is called a bridge if removing e increases the connected component of
the graph.
– The vertex u  V is called a cut vertex if removing u along with the edges
connected to u increases the connected component of the graph.
• Ex: edge (5,10 ) is bridge, vertex 6 is cut vertex.

20
Directed graph
 Semi-degree of the vertex
Definition 1. If e=(u,v) is an arc of a directed graph G, then we say that the two
vertices u and v are adjacent, and say the arc (u, v) connects the vertex u to
the vertex v, or say the arc (u, v) goes out of vertex u and into vertex v.
– The vertex u is called the initial vertex, and the vertex v is called the terminal vertex of the
arc (u,v).
Definition 2. In a graph with directed edges the in-degree of a vertex v,
denoted by deg-(v), is the number of edges with v as their terminal vertex. The
out-degree of v, denoted by deg+(v), is the number of edges with v as their
initial vertex.
(Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.)

22
Example

23
 Sum of semi-degrees of vertices
Theorem 1. Let G = <V, E> is a directed graph. Then

Note: The undirected graph that results from ignoring directions of

edges is called the underlying undirected graph.

24
 Path, cycle
Definition 1. The path of length n from vertex u to vertex v in a directed graph G=<V,E>
is the sequence x0 , x1 , . . ., xn, where n is a positive integer, u = x0 , v = xn, (xi , xi+1 )  E,
i=0,1,2,...,n-1.

• This path can be represented as a sequence of arcs: (x0 , x1 ), (x1 , x2 ), . . ., (xn-1, xn ).

• The vertex u is the initial vertex and the vertex v is the terminal vertex of the path.
• A cycle is the path that begins and ends at the same vertex.
• A path or cycle is said to be simple if no multiple edges.

25
Strongly connected and weakly connected DiGraph

Definition 2. A directed graph G=<V,E> is called strongly connected if there

is a path in each direction between each pair of vertices of the graph.

Definition 3. A directed graph G=<V,E> is called weakly connected if its

underlying undirected graph is connected.

Graph G1 is strongly connected, graph G2 is weakly connected.

26
 Directionable
(Định chiều/hướng được)
Definition 4. An undirected graph G=<V,E> is called directionable if we can
transform the edges in G into corresponding arcs to obtain a strongly
connected directed graph.

Theorem 1. An undirected graph G= < V, E > is directional if and only if its

edges are not bridge.

27
Some special simple graphs
 Complete Graph
(đầy đủ)

• A complete graph on n vertices, denoted by Kn, is a simple graph that

contains exactly one edge between each pair of distinct vertices.

Note: Kn has: n verices (each vertex of degree n-1) and n(n-1)/2 edges.

29
 Compensation graph
(Đồ thị bù)

• G' is said a complement of G if its vertices are vertices of G

and two vertices of G' are adjacent if and only if they are not
adjacent on G.

1 2 1 2

G G'
3 3
4 4

30
 Cycle (graph)
• The cycle graph Cn (n  3) has edges (1,2),(2,3),..,(n-1,n), (n,1).

• Vertices with the same degree (2)

• There n edges

31
 Wheel Graph
• Wheel graph Wn is obtained by adding a vertex joining all vertices of Cn.

Note: Wn has n+1 verices (n vertices of degree 3, a vertex of degree n) and

2n edges.

32
 (Two-sided) Bipartite graph
• A graph G = <V,E> is said to be Bipartite if its vertex set V can be partitioned
into two sets X and Y such that each edge of the graph has only the form (x,
y), where x  X and y  Y ( X  Y=V and X  Y=∅ ).

Example:

33
 Complete bipartite graph
• Bipartite graph G=(X  Y, E) with |X|= m,|Y| = n is called a complete
bipartite graph, denoted by Km,n if each vertex in set X is connected to all
vertices in set Y and vice versa.

Example: Graph K2,3 ; K 3,3 ; K 3,5

34
 Algorithm to check connected graph is Bipartite

Theorem: G is a Bipartite graph <=> G has no cycle which has odd length.

Algorithm :
1) Let v be any vertex of the graph. Set X={v}
2) Find Y is the set of adjacent vertices of the vertices in X.
a) If X  Y  then the graph is not bipartite, terminated.
b) Otherwise, go to (3) .
3) Find T is the set of adjacent vertices of the vertices in Y.
a) If T  Y  then the graph is not bipartite, terminated.
b) If T=X then the graph is bipartite, terminated. Otherwise, X=T and repeat (1) .

35
 Example of Bipartite graph
• This graph is not bipartite because it contains cycles of odd length (=3).

• This graph is not bipartite because it contains cycles of odd length (=3 ).

36
 Example of Bipartite graph (cont'd)
• This graph is bipartite because it does not contain cycles of odd length.

37
 Cube graph
(lập phương)

• The cube graph Qn is a graph that has vertices representing the 2n bit strings of
length n.
– Two vertices are adjacent if and only if the bit strings that they represent differ in exactly
one bit position.

Example: Qn with n = 0, 1, 2, 3.

38
 Planar graph
(phẳng)
• A graph is said planar if it can be drawn on a plane such that its edges
do not intersect .
• Example:

• Planar graphs have many important applications

in printed circuit technology.
• The planar representation of the graph will divide the
plane into regions (using Euler's formula), including
the unbounded domain (miền không bị chặn).

39
 Planar Graph: Euler Formula

• G is a connected planar graph, G has n vertices, m edges, r is

the number of regions of the plane divided by the plane
representation of G. We have: r = m-n + 2
• Example: m=11, n=7; number of domains r= m-n+2 = 6

40
 Planar Graph: Recognition
Corollary 1: If G is a simple planar connected graph with n vertices and m
edges, then m≤3n–6.
Corollary 2: If G is a simple planar connected graph with n vertices, m edges
and no cycles of length 3, then m≤2n–4.
Corollary 3: In a simple planar connected graph, there is always at least one
vertex of degree < 5 .
Example :
– Consider the graph K3.3 with n = 6; m = 9. We have K3.3 which is a simple connected graph
without a cycle of length 3 but does not satisfy the properties of the planar graph in
Corollary 2 (m = 9 >2n – 4 = 8). So K3.3 is not a planar graph.
– Consider the same with K5 with n = 5; m = 10. We have K 5 which is a simple connected
graph but does not satisfy the properties of the planar graph in Corollary 1 (m = 10 > 3n
– 6 = 9). So K5 is not a planar graph.

41
 Planar Graph – How to?
• Sign 1: If graph G contains a subgraph that is not planar, then G is not planar.
• Sign 2: Graph G that does not satisfy the conclusion of Corollary 1, Corollary
2 is a non-planar graph.
• Sign 3 (Kuratowski's Theorem): Graph G is not planar if and only if G
contains a subgraph that congruent (đồng dạng) with K3,3 or K5.

Definition: The graph G' is generated from G by division along edge (x, y) if G'
is obtained from G by removing edge (x, y) and adding vertex z and two edges
(x, z), (z, y).
– Graphs G1 and G2 are said congruent if they are derived from the same graph G by a series
of edge divisions.

42
 Planar graph – How to? (cont’d)
Comments: Two graphs K5 and K3,3 are the simplest non-planar graphs with
the following properties:
– If we delete a vertex or an edge of these graphs, we will get a planar
graph.
– Graph K5 is a non-planar graph with the fewest vertices.
– Graph K3,3 is a non-planar graph with the fewest edges.

43
 Planar graph – How to? (Cont’d)
Example: Check if graph G is planar? Using Kuratowski's theorem.

44
 Subgraph and partial graph (own graph)
• Let G = (V, E) is a graph.
– Graph G' = (V', E') is a subgraph of G if V'⊆V and E'⊆E.
– Graph G” = (V, E”) with E” ⊆ E is the partial graph of the graph G.
• Note:
– Each subset of vertices V' of a graph G that corresponds uniquely to a
subgraph.
• To define a subgraph, we only need to state the vertex set of it.
– An partial graph is a graph that keeps the original set of vertices and
removes some edges..

45
Subgraphs and partial graphs: Example

46
 Isomorphism
(Đẳng hình)

• Two graphs G1= (V1, E1) and G2= (V2, E2) are called isomorphism if there exists a
bijective function S (song ánh) on the sets vertices preserve (bảo toàn) edges:
∀x, y ∈ V1: (x, y) ∈ E1 ⇔ (S(x), S(y)) ∈ E2.
• The two isomorphic graphs differ only in the names of the vertices and the graphical
representation.
– Therefore, we do not distinguish two graphs isomorphic to each other.
• Two isomorphic graphs will have the same number of vertices, the same number of
vertices of degree k, the same number of edges, and the same number of connected
components.

47
 Example of isomorphism
The following two graphs are isomorphic with bijective function:
S(ai ) = x i , i = 1, 2, 3, 4.

48
 Graph Coloring
• Color the graph so that two adjacent vertices have different colors
and use the fewest number of colors possible.

Algorithm:
1) Sort the list of vertices in descending order (degree).
2) Let m be the number of colors to use, initially m=0;
3) While there are uncolored vertices {
a) m=m+1;
b) Color m the first uncolored vertex in the list.
c) Color m for uncolored vertices in the list and not adjacent to vertices of color m.
}

49
 Graph coloring: Example
• Given a simple undirected graph with 7 vertices, the adjacency matrix
form is as follows:

• Present the results at each step when applying the coloring algorithm.
50
Exercises
 Exercise 1
• Determine the degree of each vertex.
• Connected? Exist Path? Cycle?
• Bridge? Cut vertex?
• Directionable?

52
 Exercise 2
• Determine the in-degree deg- and the out-degree deg+ of each vertex.
• Weakly connected? Strongly connected?
• Exist Path? Cycle?

53
 Exercise 3
Draw an undirected graph G=(V,E) given by:
V={a,b,c,d,e,f,g}
and
E = {( e , g ),( b , f ),( d , c ),( d , f ),( c , f ), ( a , f ),( e , d )}

54
 Exercise 4
• Let f as follows:
f(A)=1, f(B)=2, f(C)=3, f(D)=4, f(E)=5, f(F)=6.

Check whether the given pair of graphs are isomorphic or not?

55
 Exercise 5
• Check if the following two graphs are isomorphic or not?

58
 Exercise 6
• For each of the following graphs, indicate whether it is a planar graph? If yes,
show how to draw.

60
 Exercise 7
There are 7 subjects, the following pairs of exams have the same students:
(1,2);(1,3);(1,4);(1,7);(2,3);(2,4);(2,5);(2,7),
(3,4);(3,7);(4,5);(4,6);(5,7);(6,7)

• Use the coloring algorithm to find the minimum number of sessions

that need to be held.

61
 Exercise 8
• There are 7 television stations located at a distance from each other as shown in
the table below. How many different channels are needed to broadcast if two
stations cannot use the same channel when they are no more than 15 km apart?

62