Graph theory glossary

1
Topics

 Basics
 Connectivity
 Paths

2
1. Basics

 Graphs and related objects

 Adjacency and incidence
 Isomorphism
 Types of graphs
 Subgraphs

3
1.1. Graphs and related objects

Graphs are mathematical structures used to model pairwise

relations between objects.

4
Undirected graph (simple graph)

A simple graph G(V,E) is a pair of sets:

 V – the set of “vertices" or "nodes“;
 E – the set of “edges” or “arcs” that connect pairs of nodes.

An edge (an undirected edge) is an unordered pair of different

vertices.
An edge e=(a,b) joins vertices a and b. The vertices a and b are
the end vertices or the ends of the edge e.

5
Undirected graph (simple graph)

Example G(V,E)

V={a,b,c,d,e,f}
E={(a,b),(a,d),(b,e),(b,c),
(b,f),(c,f),(e,f)}

 It is possible to write ab
instead of (a,b);
 ab=ba.

6
Directed graph (digraph)

If edges are ordered pairs of different nodes, then edges are

called directed edges and a graph is called directed graph or
digraph.
For an edge e=(a,b) the vertex a is its head and the vertex b is its
tail.
Example

7
Mixed graph

If both undirected and directed edges are allowed, then a graph is

called mixed graph.

Example

8
Multigraph

Edges with the same ends (or with the same head and tail) are
multiple edges.
If multiple edges are allowed, then a graph is called multigraph.
Example

9
Pseudograph

A loop is an edge whose endpoints are the same vertex (e=vv).

If loops are allowed, then a graph is called pseudograph.
Example

10
Combinations

11
Graph invariants

A graph invariant is a property of graphs that depends only on

the abstract structure, not on graph representations such as
particular labellings or drawings of the graph.
The number of vertices of a graph is its order (notation p=|V|).
The number of edges of a graph is its size (notation q=|E|).
Example
p=6
q=7

12
1.2. Adjacency and incidence

Consider an edge e=ab of a graph (directed or undirected).

The vertices a and b are incident with the edge e. The edge e is
incident with the vertices a and b.
The vertices a and b are adjacent.
Edges incident with the same vertex are adjacent.

13
Adjacency and incidence

Examples The vertices a and b are

adjacent.
The vertices a and e are not
adjacent.
The edges ab and ad are not
adjacent.
The edges be and ad are not
adjacent.
The vertex a and the edge ab
are incident.
The vertex c and the edge ab
are not incident.

14
Neighbours

Consider an undirected graph G(V,E) and a vertex aV.

The set N(a)={b: abE} is the set of neighbors of the vertex a.
Example
a b c

d e f

N(a)={b,d}

15
Neighbours

Consider a directed graph G(V,E) and a vertex aV.

The set N+(a)={b: abE} is the set of out-neighbors of the vertex a.
The set N–(a)={b: baE} is the set of in-neighbors of the vertex a.
Example
a b c

d e f

N+(a)={b}, N–(a)={d}

16
The degree of a vertex

For an undirected graph the degree of a vertex v (notation d(v)) is

the number of edges incident with v.
Examples

a b c a b c

d e f d e f

d(a)=2, d(b)=4, d(f)=3 d(a)=3, d(b)=5, d(f)=5

17
The degree of a vertex

A loop vv adds 2 to the degree of a vertex v.

Example

a b c

d e f

d(a)=2, d(b)=6, d(f)=5

18
The degree of a vertex

For a directed graph there are three characteristics:

● the out-degree of a vertex v (notation d+(v)) is the number of
edges with the tail in v:
d+(v)=|{vu: uV, vuE}|;
● the in-degree of a vertex v (notation d–(v)) is the number of
edges with the head in v:
d-(v)=|{uv: uV, uvE}|;
● the degree of a vertex v (notation d(v)) is the sum of the out-
degree and the in-degree of v:
d(v)= d+(v)+d-(v).

19
The degree of a vertex

Examples

a b c a b c

d e f d e f

d+(a)=1, d–(a)=1, d(a)=2; d+(a)=1, d–(a)=1, d(a)=2;

d+(f)=2, d–(f)=1, d(f)=3 d+(f)=4, d–(f)=1, d(f)=5

20
The degree of a vertex

Examples

a b c a b c

d e f d e f

d+(a)=1, d–(a)=1, d(a)=2; d+(a)=1, d–(a)=1, d(a)=2;

d+(f)=2, d–(f)=1, d(f)=3 d+(f)=4, d–(f)=1, d(f)=5

21
Graph invariants

Minimum degree Example

 G  min d v  δ(G)=1
vV Δ(G)=4
Maximum degree
G  max d v 
vV

22
Particular cases

 A vertex with degree 0 is called an isolated vertex.

 A vertex with degree 1 is called a leaf vertex or end vertex. This
terminology is common in the study of trees in graph theory.
 A vertex with degree n − 1 in a graph on n vertices is called a
dominating vertex.

23
Handshaking lemma (Leonhard Euler)

Lemma 1. The doubled number of edges of a finite undirected

graph is equal to the sum of the degrees of vertices:
p

 d v  2q.
v 1
Lemma 2. Every finite undirected graph has an even number of
vertices with odd degree.

24
1.3. Isomorphism

Graphs G(V,E) and G’(V’,E’) are isomorphic if there exists a

bijection φ:V→V’ such as for all x,yV:
xyE if and only if φ(x)φ(y)E’.

Isomorphic graphs are not distinguished.

To prove that graphs are isomorphic it is necessary to find a
bijection φ.
To prove that graphs are not isomorphic it is sufficient to prove
that one graph has a certain property and another graph has
not the property.

25
Example: isomorphic graphs

a b c a f

e b

d e f d c
f

a b

d e

c
26
Example: nonisomorphic graphs

All the vertices 1, 3 and 5 (and 2, 4 and 6 ) of the graph on the left
are pairwise adjacent. There are no such three vertices in the
graph on the right.

1 2 a f

3 4 e b

5 6 d c

27
1.4. Types of graphs

A graph is complete if all its vertices are pairwise adjacent.

A complete graph with p vertices is denoted as Kp.
The number of the edges of Kp is equal to p(p–1)/2.

K4 K5

28
Types of graphs

A graph is empty if any pair of

its vertices are not adjacent
(E=Ø).

A graph is k-regular (regular)

if all its vertices have the
same degree k.

29
Types of graphs

A graph is two-partite (bipartite, bigraph) if the set of its vertices

can be divide into two subsets V1 and V2 so that every edge
connect vertices from different subsets, i.e.
V= V1UV2, V1∩V2 =Ø, for all xyE: x  V1, y  V2.

30
Types of graphs

A graph is complete two-partite (bipartite, bigraph) if every

vertex from V1 is adjacent with every vertex from V2, i.e.
V= V1UV2, V1∩V2 =Ø, for all x  V1, y  V2.: xyE.

A complete bigraph
where |V1|=n, |V2|=m
is denoted as Knm.
K3,3

31
Types of graphs

A graph is trivial if |V|=1, |E|=0.

32
1.5. Subgraphs

Consider two graphs: G(V,E) and G’(V’,E’).

If V’V and E’E then G’ is a subgraph of G (less formally, G
contains G, notation G’G).
Example.

a b c a b

d e f d e f

G(V,E) G’(V’,E’)

33
Subgraphs

If G’G and E’ contains all the edges xyE: x,yV’, then G’ is an

induced subgraph of G.
We say that V’ induces G’ in G and write G’=G[V’].
Example.
a b c a b

d e f e f

G(V,E) G’=G[{a,b,e,f}]

34
Subgraphs

If V’=V then G’ is a spanning subgraph of G.

Example.

a b c a b c

d e f d e f

G(V,E) G’(V,E’)

35
Subgraphs

If V’≠V and E’≠E then G’ is a proper subgraph of G.

a b c a b c

d e f e f

G(V,E) G’(V’,E’)

36
2. Connectivity

 Walks
 Distances
 Connectivity of simple graphs
 Connectivity of directed graphs

37
2.1. Walks

A walk is a sequence of vertices and edges

<v0, vn>=v0e1v1…vi–1eivi…vn–1envn,
where ei=vi–1vi. A walk is closed if its first and last vertices are the
same, and open if they are different.
If there are no multiple edges then it is possible to omit edges
α β
Examples. a b c a b c

γ δ ε ζ η θ κ

d e f d e f
λ

<a,f> = a α b ζ f η c θ f κ c β b ζ f <a,f> = a b f c f c b f
38
Trail and tour

A trail is an open walk in which all the edges are different.

A tour (or a circuit) is a closed walk in which all the edges are
different.
Examples.
a b c

Trail <a,f> = a b f c b e f

Tour <a,a> = a b f c b e a

d e f

39
Path and cycle

A path (or a chain) is an open walk in which all the vertices (and
hence the edges) are different.
A cycle (or a circuit) is a closed walk in which all the vertices
are distinct.
Examples.
a b c

Path <a,f> = a b e f

Cycle <a,a> = a b f e a

d e f

40
2.2. Distances

The length of a walk is the number of edges that it uses.

The shortest path <u,v> is a path of minimal length | <u,v> |.
The distance between two vertices d(u,v) is the length of a
shortest path <u,v>, if one exists, and otherwise the distance
is infinity.
Examples.
α β
a b c
<a,f> = a α b ζ f η c θ f κ c β b ζ f
|<a,f>| = 7
γ δ ε ζ η θ κ
Shortest path <a,f> = a α b ζ f
d(a,f) = 2
d e f
λ
41
Distances
The eccentricity ε(v) of a vertex v is the maximum distance from
v to any other vertex.

The diameter D(G) of a graph G is the maximum distance

between two vertices in a graph or the maximum eccentricity
over all vertices in a graph.

The radius R(G) is the minimum eccentricity over all vertices in a

graph.
.

42
Distances

Vertices with maximum eccentricity are called peripheral

vertices.
Vertices of minimum eccentricity form the center.
Examples.

a b c ε(a)=ε(b)=2
ε(c)=ε(d)=ε(e)=ε(f)=3
R(G)=2
D(G)=3
Peripheral vertices c, d, e, f
Centre a, b
d e f

43
2.3. Connectivity of simple graphs

If it is possible to establish a path <u,v> from vertex u to other

vertex v, the vertices u and v are connected.
If all the pairs of vertices are connected, the graph is said to be
connected; otherwise, the graph is disconnected.
Examples.
a b c a b c

d e f d e f

44 Connected graph Disconnected graph

Connected component

A connected component of a graph G(V,E) is any of its

maximally connected subgraph, i.e. an induced subgraph
which is not a proper subgraph of any other connected
subgraph of G(V,E) .
Examples.
a b c b c b c

d e f e f e f

Graph with two components Component Not a component

45
Articulation point and bridge

An articulation point (or separating vertex) of a graph is a

vertex whose removal from the graph increases its number of
connected components.
A bridge, or (cut edge) is an analogous edge.

Examples.
de – bridge
d, e, h – articulation
points

46
Cuts

A vertex cut, (or separating set) of a connected graph G is a

set of vertices whose removal makes G disconnected or
trivial.
Analogous concept can be defined for edges.
Examples.
a b c

{ b, e } – vertex cut

{ ab, be, ef } – edge cut

d e f

47
Graph invariants

k(G) – the number of connected components

The vertex connectivity κ(G) is the size of a minimal vertex cut.
The edge connectivity λ(G) is the size of a smallest edge cut.
A graph is called n-vertex-connected (n-edge-connected) if its
vertex (edge) connectivity is n or greater.
κ(G) ≤ λ(G) ≤ δ(G)
Examples. a b c

κ = 2 (vertices d, e)

λ = 2 (edges ad, de)

d e f

48
Cuts for a pair of vertices

A vertex cut S(u,v), (or separating set) for two connected

vertices u and v is a set of vertices whose removal mekes the
vertices u and v disconnected.
Analogous concept can be defined for edges.
Examples.

a b c

Vertex cut S(a,f)={b,d,e}

Edge cut S(a,f)={ab,ae,ef}

d e f

49
Menger theorem

50
2.4. Connectivity of directed graphs

If it is possible to establish a path <u,v> and a path <v,u> in a

digraph, the vertices u and v are strongly connected.
If it there exists either a path <u,v> or a path <v,u> in a digraph,
the vertices u and v are unilaterally connected.
If it there exists a path <u,v> in a graph obtained from a digraph
by canceling of edges direction, the vertices u and v are
weakly connected.
Examples.
u v u v u v

Strongly connected Unilaterally connected Weakly connected

51
Connectivity of directed graphs

If all the pairs of vertices of a digraph are strongly / unilaterally /

weakly connected, the digraph is strongly / unilaterally /
weakly connected.
Examples.

Strongly connected Unilaterally connected Weakly connected

52
Strongly connected component

A strongly connected component of a digraph G(V,E) is any its

maximally strongly connected subgraph, i.e. an induced
subgraph which is not a proper subgraph of any other strongly
connected subgraph of G(V,E) .
Example.

53
Quotient graph

The quotient graph of a digraph D(V,E) with k strongly connected

components induced by sets of vertices V 1,…,Vk is a graph
D’(V’,E’) where V’={v1,…,vk}, vivjE’ if there is an edge uiuj E:
ui Vi, uj Vj.
Example.

54 Digraph Quotient graph

3. Paths

 Graph traversal
 Shortest path

55
3.1. Graph traversal

Graph traversal is the problem of visiting all the vertices in a

graph, updating and/or checking their values along the way.
Breadth-first search (BFS) is a graph traversal algorithm that
begins at a start vertex and explores all its neighbors (out-
neighbors for a digraph). Then for each of those nearest
vertices, it explores their unexplored neighbors, and so on,
until all the vertices are visited.
Depth-first search (DFS) is a graph traversal algorithm that
begins at a start vertex, explores its not visited neighbor and
then considers that neighbor as a start vertex. If all the
neighbors are visited then “backtracking” is used, i.e. the
previous vertex is considered as a start vertex.

56
Graph traversal examples

BFS DFS

57
3.2. Shortest path

The shortest path <u,v> is a path of minimal length | <u,v> |.

Lee algorithm (based on the DFS) is usually used to find the
shortest path.
Example.

58
Shortest path

A weighted graph associates a label (weight) with every edge

in the graph.
The weight of a path W(<u,v>) is the sum of weights of the
edges included in the path.
The shortest path <u,v> in a weighted graph is a path of minimal
weight W(<u,v>) .
Example.

59
Shortest paths problems
 The single-pair shortest path problem, in which we have to
find shortest paths from a source vertex v to a single
destination vertex u.
 The single-source shortest path problem, in which we have
to find shortest paths from a source vertex v to all other vertices
in the graph.
 The single-destination shortest path problem, in which we
have to find shortest paths from all vertices in the directed
graph to a single destination vertex v.
 The all-pairs shortest path problem, in which we have to find
shortest paths between every pair of vertices v, u in the graph.

60
Shortest paths algorithms

 Dijkstra's algorithm solves the single-source shortest path

problem.
 Bellman–Ford algorithm solves the single-source problem if
edge weights may be negative.
 Floyd–Warshall algorithm solves all pairs shortest paths.

61
4. Location problems

 Distances in a weighted graph

 Centre
 Median
 Extencions
 Absolute P-centre
 P-median

62
4.1. Distances in a weighted graph

 Vertex-vertex distance
 Point-vertex distance
 Vertex-point distance
 Vertex-edge distance

63
Vertex-vertex distance

The vertex-vertex distance between vertices i and j

(notation d(i,j)) is the weight of the shortest path <i,j>.
It can be found by the Floyd–Warshall algorithm.
Example.

64
F-point

Consider an edge e=(i,j) with the weight cij>0 and a

parameter f : 0≤f ≤1.
The point at the edge which divide the edge in
proportion f : (1–f) is called the f-point (notation f(i,j)).

The weight of the edge part if is equal to fcij, the weight

of the part fj is equal to (1–f)cij.
The vertex i is 0-point, the vertex j is 1-point.
The other points are interior.
65
Point-vertex distance

The point-vertex distance between a point f(i,j) and a

vertex k (notation d(f(i,j),k)) is the weight of the
minimal path < f(i,j),k>.
For an undirected edge (i,j):

66
Point-vertex distance

The dependence d(f(i,j),k)) of f can be one of three types.

67
Point-vertex distance

The maximum point f* is the point of the lines intersection:

=

Since

so f*[0,1].
68
Point-vertex distance

Example:

69
Point-vertex distance

Example:

70
Point-vertex distance

For a directed edge (i,j):

71
Point-vertex distance

Example:

72
Point-vertex distance

Example:

73
Vertex-point distance

The vertex-point distance between a vertex k and a point

f(i,j) (notation d(k, f(i,j))) is the weight of the minimal path
<k, f(i,j)>.

For an undirected edge ij:

For a directed edge ij:

74
Vertex-point distance

Example (undirected edges):

75
Vertex-point distance

Example (directed edges):

76
Vertex-edge distance

The vertex-edge distance between a vertex k and an edge ij

(notation d(k,(i,j))) is the maximum vertex-point distance
d(k, f(i,j)):

For a directed edge (i,j) the maximum point f*=1 and the
vertex-edge distance

77
Vertex-edge distance

Example
(directed
edges):

78
Vertex-edge distance

For an undirected edge (i,j) the dependence d(k,f(i,j)) of f can

be one of three types.

79
Vertex-edge distance

Example
(undirected
edges):

80
Point-edge distance

The point-point distance between a point f(i,j) and a point

g(k,l) (notation d(f(i,j),g(k,l))) is the weight of the minimal
path <f(i,j),g(k,l)>.
The point-edge distance between a point f(i,j) and an edge
(k,l) (notation d(f(i,j),(k,l))) is the maximum point-point
distance d(f(i,j),g(k,l)):

81
Point-edge distance

For an undirected edge (i,j)≠(k,l) the minimal path can pass

through the vertex i or the vertex j:

82
Point-edge distance

Example (undirected edge):

83
Point-edge distance

For a directed edge (i,j)≠(k,l) the minimal path can pass only
through the vertex j:

84
Point-edge distance

Example (directed edge):

85
Point-edge distance

For an undirected edge (i,j)=(k,l) and f<1/2 the most distant

points g are close to the vertex j. If d(i,j)<ci,j then the
minimal path <f(i,j),g(i,j)> can pass through the vertex i:

86
Point-edge distance

The maximum point g* is the point of the lines intersection:

Hence

87
Point-edge distance

If the minimal path <f(i,j),g(i,j)> passes only through the edge

(i,j) then:

The maximum point g*=1.

88
Point-edge distance

Hence the point-edge distance for f<1/2

This distance is maximum for f=0 and minimum for f=1/2.

The minimum distance is equal to ci,j/2.

89
Point-edge distance

For an undirected edge (i,j)=(k,l) and f>1/2 the most distant

points g are close to the vertex i. If d(j,i)<cj,i then the
minimal path <f(i,j),g(i,j)> can pass through the vertex j:

90
Point-edge distance

The maximum point g* is the point of the lines intersection:

Hence

91
Point-edge distance

If the minimal path <f(i,j),g(i,j)> passes only through the edge

(i,j) then:

The maximum point g*=0.

92
Point-edge distance

Hence the point-edge distance for f>1/2

This distance is maximum for f=1 and minimum for f=1/2.

The minimum distance is equal to ci,j/2.

93
Point-edge distance

Finally, the point-edge distance is

94
Point-edge distance

Example
(undirected
edges):

95
Point-edge distance

Example (undirected edges):

96
Point-edge distance

For a directed edge (i,j)=(k,l) the most distant points g are

situated between the vertex i and the point f close to the
point f .
d(j,i)

i g f j

97
Point-edge distance

Example
(directed
edges):

98
Maximum distances

Maximum vertex-vertex:

Maximum point-vertex:

Maximum vertex-edge:

Maximum point-edge:

99
Total distances

Total vertex-vertex:

Total point-vertex:

Total vertex-edge:

Total point-edge:

10
4.2. Centers of a graph

 Center
 General center
 Absolute center
 General absolute center

10
Center

A center of graph G is any vertex v of graph G such that

Example. Vertex c is the center.

10
General center

A general center of graph G is any vertex v of graph G such that

Example. Vertex a is the general center.

10
Absolute center

An absolute center of graph G is any point g of graph G such that

Theorem. No interior point of a directed edge can be an absolute

center.

Point f* of an undirected edge can be a candidate for absolute

center if it is gives the minimal value of the upper portion of the
point-vertex distance from point f* to all the vertices.

10
Absolute center

Example.

10
Absolute center

Example. Edge δ=(a,c).

10
Absolute center

Example. Edge α=(a,b).

10
Absolute center

Example. Edge ζ=(b,d).

10
Absolute center

Example. Plots of point-vertex distances.

10
Absolute center
Example.
For edge δ=(a,c):

For edge α=(a,b): f*=0 (vertex a).

For edge ζ=(b,d):

Absolute center: point 3/14 δ, MPV(3/14 δ)=5,5.

11
General absolute center

An general absolute center of graph G is any point g of graph G

such that

Theorem. If an interior point of a directed edge is a general

absolute center then its end is also a general absolute center.

Point f* of an undirected edge can be a candidate for general

absolute center if it is gives the minimal value of the upper
portion of the point-edge distance from point f* to all the edges.

11
General absolute center

Example.

11
General absolute center

Example. Plots of point-edge distances. Vertex a is the general

absolute center.

11
4.3. Medians of a graph

 Median
 General median
 Absolute median
 General absolute median

11
Median

A median of graph G is any vertex v of graph G such that

Example. Vertex c is the median.

11
General median

A general median of graph G is any vertex v of graph G such that

Example. Vertex a is the general median.

11
Absolute median

An absolute median of graph G is any point g of graph G such that

Theorem. There is always a vertex that is an absolute median.

Example. Vertex c is the median and the absolute median.

11
General absolute median

A general absolute median of graph G is any point g of graph G such

that

Theorem. No interior point of a directed edge can be a general absolute

median.
Theorem. There is always a vertex or the middle point of an undirected
edge that is a general absolute median.

11
General absolute median

11
General absolute median

Example.

12
General absolute median

Example.

12
General absolute median

Example

Vertex a is the general absolute median.

12
4.4. Extensions

 Weighted location
 Multicentres and multimedians

12
Weighted location

Suppose that different weights W(j) (W(i,j)) are associated with vertex j
(edge (i,j)). This weights can be considered as probabilities or
frequencies of visiting the vertex or the edge.
Vertex-vertex distance:

Vertex-edge distance:

12
Multicentres and multimedians

Let Xr be a subset of points of graph G(V,E) containing r points.

Set-vertex distance d(Xr,j) is the minimum distance between any one of
the points in set Xr and vertex j; i.e.

Set-edge distance d(Xr,(k,l)) is the minimum distance between any one of

the points in set Xr and edge (k,l), i.e.

12
Multicentres and multimedians

Example. X3={c,(2/7)δ,(1/2)α}

12
Multicentres and multimedians

Example.

12
Multicentres and multimedians

Example.

12
Multicentres and multimedians

Multicenter and multimedian problems arise when there is a need to

locate a number of facilities in the best possible way. The following
distances can be minimize:
 Maximum set-vertex distance (MSV)
 Maximum set-edge distance (MSE)
 Total set-vertex distance (TSV)
 Total set-edge distance (TSE)

12
4.5. Absolute multicentres

Problems:
 (a) Find the optimal location anywhere on the graph of a given
number (say p) of centres so that the distance required to reach the
most remote vertex from its nearest centre is a minimum.
 (b) For a given "critical" distance, find the smallest number (and
location) of centres so that all the vertices of the graph lie within this
critical distance from at least one of the centres.

13
4.6. Multimedians

Problems:
 (a) Find the optimal location anywhere on the graph of a given
number (say p) of medians so that the total distance required to reach
all the vertices from its nearest median is a minimum.
 (b) For a given "critical" distance, find the smallest number (and
location) of medians so that the total distance required to reach all the
vertices from its nearest median lie within this critical distance.

13
Problem statement

Xp – multimedian (p-median)
v Xp – median vertex
v Xp – non-median vertex

Vertex j is allocated to vertex i if vertex i is a median vertex and

d(Xp,j)=d(i,j).
Any median vertex i is allocated to vertex i.

13
Agenda
 1. Adjacency Matrix of a Graph
 2. Incidence Matrix of a Graph
 3. Adjacency Lists
 4. Trees and Properties of Trees
 5. Characterization of Trees
 6. Centers of Trees
 7. Rooted Trees
 8. Binary Trees
 9. Spanning Trees and Forests
 10. Spanning Trees of Complete Graphs
 11. Application to Electrical Networks
 12. Minimum Cost Spanning Trees
Adjacency Matrix of a Graph

 Definition: A square matrix used to represent a finite graph.

 Structure: Rows and columns represent vertices. The value at

position (i, j) is 1 if there is an edge between vertices i and j;
otherwise, it is 0.

 Properties:
– Symmetric for undirected graphs.
– Useful for graph algorithms (e.g., finding paths, connectivity).
Incidence Matrix of a Graph
 Definition: A matrix representing the relationship between vertices and
edges.

 Structure: Rows correspond to vertices, columns correspond to edges.

The value is 1 if the vertex is incident to the edge, 0 otherwise.

 Properties:
– For undirected graphs: each column has exactly two 1s (the two vertices the edge
connects).
Adjacency Lists

 Definition: A collection of lists used to represent a

graph, where each vertex has a list of adjacent
vertices.

 Properties:
 - Efficient in terms of space, especially for sparse
graphs.
 - Provides quick access to adjacent nodes.
Trees and Properties of Trees

 Definition: A tree is a connected, acyclic graph.

 Properties:
– There is exactly one path between any two vertices.
– Removing any edge will disconnect the tree.
– A tree with n vertices has n-1 edges.
Characterization of Trees

 Properties:
– A graph is a tree if it is connected and has no cycles.
– Every connected graph with n vertices and n-1 edges is a
tree.
– Recursive structures can define trees.
Centers of Trees

 Definition: The center of a tree consists of one or two

central vertices that minimize the maximum distance
to any other vertex.

 Properties:
– Trees have one or two centers.
– The center is used to analyze the structure and properties
of the tree, such as in network design.
Rooted Trees

 Definition: A tree in which one vertex is designated

as the root, and all edges are directed away from the
root.

 Properties:
– Every edge points from a parent node to a child node.
– Commonly used in hierarchical structures and algorithms.
Binary Trees

 Definition: A rooted tree in which each node has at

most two children.

 Types:
– Full Binary Tree: Every node has 0 or 2 children.
– Complete Binary Tree: All levels are filled except possibly the
last, which is filled from left to right.

 Applications:
– Data structures (e.g., binary search trees, heaps).
Spanning Trees and Forests

 Definition:
 - A spanning tree is a subgraph that includes all
vertices of the graph and is a tree.
 - A forest is a collection of trees.

 Properties:
– Every connected graph has at least one spanning tree.
– Spanning trees are fundamental in network design.
Spanning Trees of Complete
Graphs

 Definition: A spanning tree of a complete graph is a

subgraph that includes all vertices and is a tree.

 Key Points:
– The number of spanning trees of a complete graph with n
vertices is n^(n-2) (Cayley's formula).
– Applications in optimal communication network design.
Application to Electrical Networks

 Overview:
– Spanning trees model electrical circuits, where the tree
represents possible paths for current.
– Kirchhoff's theorem helps calculate the number of spanning
trees and analyze network stability.
Minimum Cost Spanning Trees
 Definition: A spanning tree that minimizes the total edge cost in a
weighted graph.

 Algorithms:
– Kruskal’s Algorithm: Greedy algorithm that adds edges with the
lowest weight until the spanning tree is complete.
– Prim’s Algorithm: Grows the tree by adding the smallest edge
that connects a vertex in the tree to a vertex outside the tree.

 Applications: Network design, routing, and optimizing resources.

Simple Graph – Degree Sequence -
Graphical or Not?

 Havel-Hakimi Algorithm: This is an iterative algorithm that

checks whether a degree sequence can correspond to a graph.

 Here's how it works - Steps:

Remove the first element (let's call it 𝑑1) and then subtract 1 from the next
– Sort the degree sequence in non-increasing order (largest to smallest).

𝑑1 elements of the sequence.

–

– Check if any element in the sequence becomes negative. If so, the

sequence is not graphical.
– Repeat the process with the new degree sequence (ignoring any zeros) until
either:
 You successfully reduce the sequence to all zeros (in which case, the sequence is graphical), or
 A negative degree appears (in which case, the sequence is not graphical)
Simple Graph – Degree Sequence -
Graphical or Not?

 Erdős-Gallai Theorem: This is a more theoretical approach,

providing a necessary and sufficient condition for a degree
sequence to be graphical.

 Theorem:A non-increasing sequence 𝑑1≥𝑑2≥⋯≥𝑑𝑛 is graphical

if and only if:

For every 𝑘 where 1≤𝑘≤𝑛,

– The sum of the degrees is even, and
–

– If these two conditions hold, then the degree sequence is graphical.

Simple Graph – Degree Sequence -
Graphical or Not?

 Erdős-Gallai Theorem: This is a more theoretical approach,

providing a necessary and sufficient condition for a degree
sequence to be graphical.

 Theorem:A non-increasing sequence 𝑑1≥𝑑2≥⋯≥𝑑𝑛 is graphical

if and only if:

For every 𝑘 where 1≤𝑘≤𝑛,

– The sum of the degrees is even, and
–

– If these two conditions hold, then the degree sequence is graphical.

Complement of Graph
 Definition: Given a graph G = (V, E), the complement of G, denoted by G', is another graph with the same
vertex set V and an edge between any two vertices if and only if there is no edge between them in G.
 In simpler terms: Think of the complement as a "flipped" version of the original graph. Where there was no
edge in G, there is one in G', and vice versa.
 Example:
 Original Graph: A graph with 4 vertices (A, B, C, D) and edges between A and B, and C and D.
 Complement: A graph with the same vertices, but with edges between A and C, A and D, B and C, and B
and D.
 Properties of Complements:
 If G is complete (every pair of vertices has an edge), then G' is empty (no edges).
 If G is connected, then G' is disconnected.
 The degree of a vertex in G' is equal to the number of vertices minus the degree of the same vertex in G.
 Applications:
 Network Analysis: To study the relationships between nodes in a network, the complement can provide
insights into the missing connections.
 Graph Theory: Complements are used in various graph algorithms and theorems, such as the theorem of
König.
Number of non-isomorphic
induced sub-graphs
 An induced subgraph is a subgraph obtained by removing a set of vertices and
all edges incident to them.

 Two subgraphs are isomorphic if there exists a bijection between their vertex
sets that preserves adjacency.

 Calculating the exact number of non-isomorphic induced subgraphs for a

given graph can be computationally challenging, especially for larger graphs. A
simple (brute force!!) approach is given below:

– Generate all possible subsets of vertices.

– For each subset, create the corresponding induced subgraph.
– Check isomorphism between each pair of generated subgraphs.
– Count the number of unique (non-isomorphic) subgraphs.
Non-isomorphic induced sub-
graphs - Examples
 Complete Graph (K_n): A complete graph with n vertices has 2^n non-isomorphic induced subgraphs. This
is because every subset of vertices can form a unique induced subgraph.

 Cycle Graph (C_n):The number of non-isomorphic induced subgraphs of a cycle graph C_n depends on
the value of n.For n = 3, there are 4 non-isomorphic induced subgraphs: the empty graph, the single vertex
graph, the path graph P_2, and the cycle graph C_3 it self. For larger values of n, the number of non-
isomorphic induced subgraphs increases.

 Path Graph (P_n):The number of non-isomorphic induced subgraphs of a path graph P_n is equal to the
number of partitions of n. For example, P_4 has 5 non-isomorphic induced subgraphs: the empty graph, the
single vertex graph, the path graph P_2, the path graph P_3, and the path graph P_4 itself.

 Star Graph (S_n): The number of non-isomorphic induced subgraphs of a star graph S_n is equal to n +
1.This is because the star graph has a central vertex and n leaf vertices. Any subset of the leaf vertices can
form a unique induced subgraph, and there are n + 1 such subsets (including the empty set).

 Complete Bipartite Graph (K_{m,n}): The number of non-isomorphic induced subgraphs of a complete
bipartite graph K_{m,n} is quite complex and depends on the values of m and n. In general, it involves
counting the number of ways to partition the vertices into two sets and then considering the possible edges
within each set and between the sets.
Eulerian Graphs
 An Eulerian graph: is a graph that has an Eulerian circuit, which is a closed trail that visits every edge
exactly once. In other words, it's possible to start at a vertex, traverse every edge of the graph exactly once,
and return to the starting vertex without repeating any edges.

 Necessary and Sufficient Condition / Eulerian Theorem:

– A connected graph is Eulerian if and only if all its vertices have even degrees.

 Eulerian Path: If a graph is not Eulerian but has exactly two vertices of odd degree, it has an Eulerian path,
which is a trail that visits every edge exactly once but doesn't necessarily start and end at the same vertex.
The two vertices of odd degree will be the starting and ending points of the Eulerian path.

 Examples :
– Complete Graph (K_n): All complete graphs are Eulerian since every vertex has a degree of n-1,
which is even for any n > 1.
– Cycle Graph (C_n): All cycle graphs are Eulerian as each vertex has a degree of 2.
– Petersen Graph: This well-known graph is not an Eulerian graph because Each vertex in this graph
has a degree of 3, which is odd.
– Eulerian Networks: Many real-world networks, such as transportation networks or street networks,
can be represented as Eulerian graphs if they are connected and all vertices have even degrees. For
example, a postman's route in a city with a connected network of streets can often be represented as
an Eulerian circuit.
Eulerian Graphs – Contd…
1. Euler Graph (Eulerian Graph): A graph is called an Eulerian graph if it contains an Euler circuit, meaning it
is possible to traverse the entire graph and return to the starting point by following each edge exactly once.
For a graph to be Eulerian, all vertices must have an even degree (i.e., an even number of edges connected
to them).

2. Euler Path (Eulerian Path): An Euler path is a path in a graph that visits every edge exactly once, but it
does not necessarily return to the starting point. A graph contains an Euler path if it has exactly two vertices
of odd degree and all other vertices have even degrees.

3. Euler Circuit (Eulerian Circuit): An Euler circuit is a special type of Euler path where the path starts and
ends at the same vertex. It visits every edge of the graph exactly once, forming a closed loop. A graph has
an Euler circuit if and only if all vertices have even degrees.

4. Euler Trail: An Euler trail is another term for an Euler path, emphasizing that the traversal is a trail in which
every edge is visited exactly once. It can start and end at different vertices. Therefore, a graph has an Euler
trail if it contains exactly two vertices of odd degree.

5. Applications: Solving routing problems like the Konigsberg Bridge Problem.

Eulerian Graphs - Problems
1. Determine the length of the Eulerian circuit in a complete graph with 10 vertices.

2. Given a graph with 8 vertices and 15 edges, where two vertices have odd degrees (3 and 5),
determine the length of the Eulerian path.

3. Verify if the Petersen graph has an Eulerian circuit.

4. Given a graph with 6 vertices and the following degrees: 2, 2, 4, 4, 4, 4, determine if it has an
Eulerian circuit.

5. A city has a street network with 12 intersections. Some intersections have an odd number of streets
connected to them. Determine if it's possible for a postman to deliver mail to every house exactly
once, starting and ending at the post office.

6. Generate a random graph with 10 vertices and 20 edges. Determine if it has an Eulerian circuit.
Bipartite Graphs
 A Bipartite Graph is a graph whose vertex set can be divided into two disjoint sets, such that no two
vertices within the same set are adjacent.

 Definition: G = (V, E) is bipartite if V can be partitioned into two sets V1 and V2 where every edge
connects a vertex in V1 to one in V2.

 Properties: Can be tested using 2-colorability; No odd-length cycles.

 Example: Application in scheduling problems where tasks are divided between two independent groups.
Hamiltonian Graphs
 A Hamiltonian Graph is a graph that contains a cycle which visits every vertex exactly once (a
Hamiltonian cycle).

 Definition: A graph is Hamiltonian if it contains a Hamiltonian cycle.

 Hamiltonian Path: A path that visits each vertex exactly once but does not necessarily return to the
starting point.

 Applications: In optimization problems like the Traveling Salesman Problem (TSP).

Hamiltonian Cycles in Weighted
Graphs
 A Weighted Graph assigns weights to its edges, often representing costs or distances.

 Hamiltonian Cycle in a Weighted Graph: The problem of finding the Hamiltonian cycle with the
minimum total weight is a well-known NP (nondeterministic polynomial time)-complete problem.

 Traveling Salesman Problem (TSP): It is the problem of finding the Hamiltonian cycle with the minimum
total weight, which is one of the most famous NP-complete problems in computer science and
optimization.

 Applications: Used in logistics and network optimization.

 Solution techniques include heuristics and approximation algorithms like Christofides' algorithm.
Hamiltonian Cycles in Weighted
Graphs
 A Weighted Graph assigns weights to its edges, often representing costs or distances.

 Hamiltonian Cycle in a Weighted Graph: The problem of finding the Hamiltonian cycle with the
minimum total weight is a well-known NP (nondeterministic polynomial time)-complete problem.

 Traveling Salesman Problem (TSP): It is the problem of finding the Hamiltonian cycle with the minimum
total weight, which is one of the most famous NP-complete problems in computer science and
optimization.

 Applications: Used in logistics and network optimization.

 Solution techniques include heuristics and approximation algorithms like Christofides' algorithm.
Traveling Salesman Problem (TSP)
 Description: In the TSP, a salesman must visit a set of cities exactly once and return to the starting city.
Each city is connected to every other city by a road, and each road has a cost (or distance) associated
with it.

 The goal is to find a Hamiltonian cycle (a cycle that visits every city once) with the minimum total
weight (the least total travel cost or distance).

 Formally, it asks: "Given a complete weighted graph, what is the Hamiltonian cycle with the minimum total
weight?"
Eulerian vs Hamiltonian Graphs
 Eulerian Graphs:

 Definition: A graph is Eulerian if it contains an Eulerian circuit, which is a cycle that visits every edge
exactly once and returns to the starting vertex.

 Key Property: Every vertex in an Eulerian graph must have an even degree (an even number of edges
connected to it).

 Conditions:
– A graph has an Eulerian circuit if and only if:
 The graph is connected.
 Every vertex has an even degree.
 Example: A square with diagonals, where you can traverse every edge exactly once, starting and ending
at the same point.

 Applications: Eulerian graphs are often used in solving problems related to routing and traversal, such
as the famous Konigsberg Bridge Problem or street-sweeping scenarios.
Eulerian vs Hamiltonian Graphs
 Hamiltonian Graphs:

 Definition: A graph is Hamiltonian if it contains a Hamiltonian cycle, which is a cycle that visits every
vertex exactly once and returns to the starting vertex.

 Key Property: A Hamiltonian graph does not necessarily involve visiting every edge, but it requires
visiting every vertex exactly once.

 Conditions:
– There is no simple condition like in Eulerian graphs (even degree rule) to determine whether a
graph is Hamiltonian.
– However, Dirac's Theorem states that if every vertex in a graph with n vertices has a degree of at
least n/2, then the graph is Hamiltonian.

 Example: A pentagon where you can visit every vertex exactly once and return to the start.

 Applications: Hamiltonian graphs are used in optimization problems like the Traveling Salesman
Problem (TSP), where the goal is to visit every city exactly once with minimal cost.
Eulerian vs Hamiltonian Graphs
 Key Differences:

 Focus:
– Eulerian graphs focus on covering edges (traversing every edge once).
– Hamiltonian graphs focus on covering vertices (visiting every vertex once).

 Conditions:
– Eulerian graphs have a strict rule: all vertices must have even degree.
– Hamiltonian graphs have no such clear rule; it's harder to determine if a graph is Hamiltonian.

 Traversal:
– In an Eulerian circuit, you revisit vertices but cover every edge once.
– In a Hamiltonian cycle, you visit every vertex once but might skip some edges.

 In summary, Eulerian graphs are about edges, while Hamiltonian graphs are about vertices.
Eulerian vs Hamiltonian -
Problems
1. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G a Hamiltonian graph?

2. For a complete graph with 7 vertices, how many Hamiltonian cycles exist?

3. Given a graph G with 6 vertices and 9 edges, is it possible for G to be a Hamiltonian graph?

4. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G an Eulerian graph?

5. For a complete graph with 5 vertices, how many Eulerian circuits exist?

6. Given a graph G with 6 vertices and 8 edges, is it possible for G to be an Eulerian graph?

7. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G both Hamiltonian and
Eulerian?

8. For a complete graph with 6 vertices, how many graphs are both Hamiltonian and Eulerian?

9. Given a graph G with 7 vertices and 15 edges, is it possible for G to be both Hamiltonian and Eulerian?

10. Given a graph G with 8 vertices and 12 edges, is it possible for G to be both Hamiltonian and Eulerian?
Eulerian vs Hamiltonian -
Problems
1. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G a Hamiltonian graph?

2. For a complete graph with 7 vertices, how many Hamiltonian cycles exist?

3. Given a graph G with 6 vertices and 9 edges, is it possible for G to be a Hamiltonian graph?

4. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G an Eulerian graph?

5. For a complete graph with 5 vertices, how many Eulerian circuits exist?

6. Given a graph G with 6 vertices and 8 edges, is it possible for G to be an Eulerian graph?

7. Given a graph G with vertices A, B, C, D, E, and edges AB, BC, CD, DE, EA, is G both Hamiltonian and
Eulerian?

8. For a complete graph with 6 vertices, how many graphs are both Hamiltonian and Eulerian?

9. Given a graph G with 7 vertices and 15 edges, is it possible for G to be both Hamiltonian and Eulerian?

10. Given a graph G with 8 vertices and 12 edges, is it possible for G to be both Hamiltonian and Eulerian?
Deterministic vs. Nondeterministic
Computation
1. Deterministic vs. Nondeterministic Computation:

 Deterministic computation is what typical computers perform. For a given input, they follow a specific set
of rules or steps to arrive at an output. Algorithms that run on deterministic machines (like normal
computers) process one possible solution path at a time.

 Nondeterministic computation, on the other hand, is a theoretical concept. A nondeterministic machine

can explore many possible solution paths simultaneously. It "guesses" a solution and then verifies if the
guess is correct, but the important point is that it checks the correctness in polynomial time.
Deterministic vs. Nondeterministic
Computation
2. Polynomial Time (P):
 Polynomial time refers to the class of problems that can be solved by an algorithm whose running time
grows polynomially with the input size n.

 For example, if an algorithm has a time complexity of O(n2), where n is the size of the input, it is
considered to run in polynomial time.

 Problems in P can be both solved and verified in polynomial time.

3. Nondeterministic Polynomial Time (NP):

 NP is the set of decision problems for which a solution, if one exists, can be verified in polynomial time.
 In simpler terms, if you're given a "candidate" solution, you can check whether the candidate solution is
correct using a polynomial-time algorithm.

 Key point: Being in NP doesn’t mean that finding the solution is easy or fast. It only means that checking
a given solution is fast.
Deterministic vs. Nondeterministic
Computation
 Examples of NP Problems:

 Traveling Salesman Problem (TSP): Given a Hamiltonian cycle (a path visiting all cities), you can easily
compute the total weight and verify whether it's the minimum. But finding that cycle in the first place is
difficult.

 Subset Sum Problem: Given a set of numbers, is there a subset that sums to a specific number? If
you’re given a candidate subset, you can quickly sum the elements and verify if it matches the target.
However, finding that subset is computationally hard.

 3-SAT: Given a Boolean formula, is there an assignment of truth values (True/False) to variables that
makes the entire formula true? If you’re given an assignment, you can plug it into the formula and check
its validity quickly.
Deterministic vs. Nondeterministic
Computation
4. Relationship Between P and NP:
 P (Polynomial Time) is a subset of NP because any problem that can be solved in polynomial time can
also have its solution verified in polynomial time.
 The big unresolved question in computer science is whether P = NP. This means:
– Is every problem that can be verified in polynomial time also solvable in polynomial time?
– P ≠ NP: Most computer scientists believe this is true, meaning that there are some problems that
can be verified quickly but cannot be solved quickly.
– P = NP: If this were true, it would imply that all NP problems can be solved just as easily as they
can be verified, revolutionizing fields like cryptography, optimization, and more.

5. NP-Complete Problems:
 A problem is NP-complete if:
– It belongs to NP (i.e., its solutions can be verified in polynomial time).
– Every other problem in NP can be transformed (or reduced) to this problem in polynomial time.
 NP-complete problems are the hardest problems in NP. If any NP-complete problem can be solved in
polynomial time, then all NP problems can be solved in polynomial time (this would mean P = NP).
 Examples: TSP, 3-SAT, Knapsack problem.
Deterministic vs. Nondeterministic
Computation
Summary:

 Nondeterministic Polynomial Time (NP) represents problems where, if you had a lucky "guess" or a
"nondeterministic" machine, you could check whether the guess is correct in polynomial time.

 NP problems are easy to verify but may be hard to solve.

 The famous P vs NP question asks whether these problems are also easy to solve, not just verify.

 In essence, NP focuses on efficient verification, whereas P focuses on both efficient solving and
verification.
Polynomial Time (P)
 Polynomial Time (P) is a complexity class in theoretical computer science that describes decision
problems that can be solved by an algorithm in a time that is bounded by a polynomial function of the
input size. This means that as the input size increases, the time required to solve the problem grows at a
relatively slow rate.

 Key characteristics of P problems:

 Efficiency: There exists an algorithm that can solve the problem in polynomial time.

 Scalability: The problem can be solved efficiently even for large input sizes.

 Examples of P problems:
 Sorting algorithms: Algorithms like quicksort, mergesort, and bubble sort can sort a list of elements in
polynomial time.

 Matrix multiplication: There are efficient algorithms for multiplying matrices in polynomial time.

 Graph search algorithms: Algorithms like breadth-first search and depth-first search can find paths in a
graph in polynomial time.
Polynomial Time (P)
 Relationship to NP:
 P is a subset of NP: Every problem that can be solved in polynomial time can also be verified in
polynomial time. Therefore, P is a subset of NP.

 P vs. NP: One of the most famous open problems in computer science is whether P is equal to NP. If P =
NP, it would mean that every NP problem could be solved efficiently, which would have profound
implications for many areas of computer science and mathematics. However, most experts believe that P
≠ NP.

 In summary:
 Polynomial time: Problems that can be solved efficiently.

 Nondeterministic polynomial time: Problems that can be verified efficiently, but finding a solution might
be difficult.

 P vs. NP: A fundamental question in computer science about the relationship between these two classes.
Nondeterministic Polynomial Time
(NP)
 Nondeterministic Polynomial Time (NP) is a complexity class in theoretical computer science that
describes decision problems that can be verified in polynomial time. This means that if a solution is
provided, its correctness can be checked efficiently. However, finding the solution itself might be
computationally difficult.

 Key characteristics of NP problems:

 Verification: Given a solution, it can be checked in polynomial time.
 Existence: It's not known how to efficiently find a solution for every instance.
 Certifiability: If a solution exists, it can be certified in polynomial time.

 Examples of NP problems:
 Traveling Salesman Problem: Given a list of cities and the distances between them, find the shortest
possible route that visits each city exactly once and returns to the starting city.
 Satisfiability Problem (SAT): Given a Boolean formula, determine if there exists an assignment of truth
values to the variables that makes the formula true.
 Clique Problem: Given a graph and an integer k, determine if the graph contains a clique (a subgraph
where every vertex is connected to every other vertex) of size k.
Nondeterministic Polynomial Time
(P)
 P vs. NP:
 One of the most famous open problems in computer science is whether the class P (problems that can be
solved in polynomial time) is equal to the class NP. If P = NP, it would mean that every NP problem could
be solved efficiently, which would have profound implications for many areas of computer science and
mathematics. However, most experts believe that P ≠ NP.

 NP-hard and NP-complete:

 NP-hard: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. This
means that if an efficient algorithm were found for an NP-hard problem, it could be used to solve any NP
problem efficiently.

 NP-complete: A problem is NP-complete if it is both NP-hard and in NP. This means that it is as hard as
any other problem in NP.

 Many important problems in computer science, such as the Traveling Salesman Problem and the
Satisfiability Problem, are NP-complete.
Graph Embedding in Surfaces
 Graph Embedding Embedding a graph in a surface means drawing it on a surface (like a plane or a
sphere) without edge intersections.
– Applications: In networking, surface embeddings help in visualizing complex connections, like internet topologies on a
2D plane or even geographic surfaces.

 Planar Graph: Can be embedded in a plane without edge crossings.

The maximum number of edges in a simple planar graph with 𝑉 vertices is 3𝑉−6.
– Key Properties:

A complete graph 𝐾5 and a complete bipartite graph 𝐾3,3 are non-planar, serving as important reference points (related
–

–
to Kuratowski's theorem).

 Surface Embedding: Involves mapping the graph to surfaces like spheres, tori, or other topological
surfaces.

 Applications: Important in fields like circuit board design and geographic information systems (GIS).
Euler’s Formula
 Euler's Formula relates the number of vertices V, edges E, and faces F of a connected, planar graph:

 V-E+F=2
– V = number of vertices,
– 𝐸= number of edges,
– 𝐹= number of faces (regions bounded by edges, including the outer region).

 Applications: Used in topology to determine whether a graph can be embedded in the plane.

 Examples: For a triangle, 𝑉=3, 𝐸=3, 𝐹=2; hence, 3−3+2=2. For a cube graph drawn on a plane,
verifying Euler’s formula shows planarity.

 Implications: It’s a foundation for checking graph planarity and analyzing graph complexity.
Planar Graphs and Kuratowski’s
Theorem
 Planar Graph: A graph that can be drawn in the plane such that no edges cross.

 Kuratowski’s Theorem A finite graph is planar if and only if it contains no subgraph that is
homeomorphic to K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph on 6 vertices).

 Applications: Critical in the design of electronic circuits, where planarity minimizes crossings between
connections.
Dual of Planar Graphs
 The Dual Graph of a planar graph is constructed by placing a vertex in each face of the graph and
connecting two vertices if their corresponding faces share an edge.

 Properties:
– Vertices and Faces Correspondence: Each face of the original graph corresponds to a vertex in the
dual graph.
– Edges: Each edge in the original graph corresponds to an edge in the dual graph.
– Planarity: The dual of a planar graph is also planar.
– Dual of a Dual: The dual of the dual graph is isomorphic to the original graph.

 Example: Dual graphs are used in geographic mapping and mesh generation for 3D modeling.

 Construction:
– Prerequisites:
– The graph must be planar and embedded in the plane, meaning its edges are drawn without any
crossings.
– A face is a region bounded by edges, including the outer infinite region.
Construction of Dual Graphs
 Place a vertex inside each face of the planar graph:
– This includes one vertex for the outer (infinite) face.

 Connect vertices of the dual graph:

– For every edge in the original graph, draw a corresponding edge in the dual graph.
– The edge in the dual connects the two vertices placed in the faces that share this edge.
– If the edge separates the outer face and an inner face, connect the dual vertex of the inner face to
the dual vertex of the outer face.

 Ensure no crossings:
– Draw the dual edges so that they cross their corresponding original edges but no others.

 Iterate until all edges are processed:

– Continue this process until all edges of the original graph are accounted for in the dual.
Dual Graphs……contd…
 Uniqueness of the dual
 Double dual
 Self-dual graph
 Dual of a sub graph
 Dual of a homeomorphic graph
 Abstract dual
 Combinatorial dual
Min-Max Theorem
 Statement: These theorems provide relationships between the minimum and maximum values of certain
graph properties (like cut and flow).

 Examples: Max-Flow Min-Cut Theorem: The maximum flow in a network is equal to the minimum cut
separating the source and sink.

 Applications: Network design, flow optimization, resource allocation.

Independent Sets and Covers
 Independent Set: A set of vertices, no two of which are adjacent. Maximizing independent sets can
represent resource optimization.

 Vertex and Edge Covers:

– Vertex Cover: Set of vertices covering all edges.
– Edge Cover: Set of edges covering all vertices.

 Applications: Used in scheduling, network security, and resource allocation.

Dominating Sets
 Definition: A dominating set S in graph G is a subset of vertices such that every vertex in G is either in S
or adjacent to a vertex in S.

 Applications: Common in sensor networks and strategic positioning problems (e.g., placing signal towers
to cover a region).
Maximum Bipartite Matching
 Bipartite Graph: Vertices can be divided into two disjoint sets U and V such that every edge connects a
vertex in U to one in V.

 Matching: A matching in a graph is a set of edges without common vertices.

 Maximum Matching: Maximum set of edges in a matching.

 Applications: Resource allocation, pairing in job assignments, stable marriage problems.

Chromatic Number and
Polynomial of a Graph
 Chromatic Number of a Graph
 Definition: The smallest number of colors needed to color vertices so no two adjacent vertices share the
same color.

 Applications: Scheduling (where conflicts are edges), map coloring, and register allocation in compilers.

 Chromatic Polynomial of a Graph

 Definition: A polynomial P(G,k) that counts the number of ways to color a graph G with k colors.

 Properties:
– For small k, determines the feasibility of a given coloring.

 Applications: Analyzing color-based constraints in scheduling and resource allocation.

Chordal Graphs and Powers of
Graphs
 Chordal Graphs
 Definition: A chordal graph is a graph in which every cycle of four or more vertices has a chord (an edge
connecting two nonconsecutive vertices).

 Applications: Efficient for certain algorithms, like tree decompositions, and widely used in database
management systems.

 Powers of Graphs
 Definition: The k-th power Gk of a graph G connects vertices if they are at most k edges apart in G.

 Applications: Social network analysis, connectivity studies.

Applications of Graph Theory
Concepts

 Bipartite Graphs: Scheduling, matching problems.

 Eulerian Graphs: Solving routing and circuit design problems.

 Hamiltonian Graphs: Logistics, route optimization.

 Planar Graphs: Circuit board design, geographic information

systems.

 Dual Graphs: 3D modeling, mesh generation, and mapping.

References

 Introduction to Graph Theory by Douglas B. West.

 Graph Theory by Reinhard Diestel.
Examples