UNIT - 4 GRAPH THEORY

STRUCTURE

4.0 Learning Objectives

4.1 Introduction
4.2 Graphs and Multigraphs
4.2.1 Definition
4.2.2 Subgraphs
4.2.3 Isomorphic and Homeomorphic Graphs
4.2.4 Paths and Connectivity
4.2.5 Traversable and Eulerian Graphs
4.2.6 Labeled and Weighted Graphs
4.2.7 Complete, Regular and Bipartite Graphs
4.2.8 Graph Colorings
4.3 Planar Graphs
4.3.1 Euler’s Theorem
4.3.2 Trees and their properties
4.3.3 Spanning tree
4.4 Summary
4.5 Keywords
4.6 Learning Activity
4.7 Unit End Questions
4.8 References

4.0 LEARNING OBJECTIVES

After studying this unit, you will be able to:

 Define a graph, identifying edges and vertices.

 Understand the basics of graph theory and their various properties.
 Find the degree of a vertex.
 Define the properties of bipartite graphs, particularly in trees.
 Reason from definitions to construct mathematical proofs.

67
  Apply graph theory concepts to solve real world applications.
 Find the shortest path through a graph using Warshall’s Algorithm and Pruning
Algorithm.
 Understand the history of Konigsberg Bridge Problem
 Identify Euler circuits and paths

4.1 INTRODUCTION

Although it is sometimes viewed as one of the more contemporary areas of mathematics, graph
theory has been around since 1736. The pioneering work on what is now known as graph theory
was published in that same year by Leonhard Euler. In the publication, Euler created a theory
that addressed the infamous Konigsberg Bridge conundrum.
There are probably not many other branches of the subject that can have a "birthday" as specific
as this. However, it must be acknowledged that graph theory is in fact a modern discipline. The
first text on graph theory was published in 1936, exactly 200 years after Euler's work, marking
its "coming of age." (Biggs et al. (1976), which includes excerpts from many of the earliest
works associated with the evolution of graph theory, provides a delightfully detailed overview
of the first 200 years of graph theory.)
The concept of a graph is extremely straightforward, much like many other ideas we have
thought about. The fact that graph theory has found many uses recently in disciplines as diverse
as chemistry, computer science, economics, electronics, and linguistics is probably due to its
simplicity.
Graphs are extremely flexible mathematical structures that may be represented on a computer,
enabling the reuse of established methods for brand-new applications without the need for
rewriting. This section explains various practical families of graphs as well as some of the
fundamental terms and operations required for studying graphs.
For mathematical applications, a more exact definition is needed. We must first declare the set
of a graph's vertices and the set of its edges in order to define it. Then, we must specify, using
exact mathematics, which edges connect which vertices. Since an edge is defined as having a
vertex at either end, we must assign endpoint vertices to each edge in the graph. An edge's
endpoints are either two vertices (if it connects two distinct vertices) or one vertex (if it
connects a vertex to another vertex).

68
 4.2 GRAPHS AND MULTIGRAPHS

In this part, we will study the discrete structures that form the basis of formulating many a
real-life problem.
The two discrete structures that we will cover are graphs and trees. A graph is a set of points,
called nodes or vertices, which are interconnected by a set of lines called edges. The study of
graphs, or graph theory is an important part of a number of disciplines in the fields of
mathematics, engineering and computer science.
What is a Graph?
A graph (denoted as G= (V, E)) consists of a non-empty set of vertices or nodes V and a set
of edges E.
Example − Let us consider, a Graph is G=(V,E)
where V= {a, b, c, d} and E={{a, b},{a, c},{b, c},{c, d}}

Fig :3.1: A Graph

Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the
number of edges incident with the vertex V.

Degree Even / Odd

Vertex

a 2 Even

b 2 Even

c 3 Odd

69
 d 1 Odd

Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex
and if the degree of a vertex is odd, the vertex is called an odd vertex.
Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the
above graph the degree of the graph is 3.
The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal
to twice the number of edges.
Multigraph

In mathematics, and more specifically in graph theory, a multigraph is a graph which is

permitted to have multiple edges (also called parallel edges), that is, edges that have the same
end nodes. Thus two vertices may be connected by more than one edge.
There are two distinct notions of multiple edges:
 Edges without own identity: The identity of an edge is defined solely by the two
nodes it connects. In this case, the term "multiple edges" means that the same edge
can occur several times between these two nodes.
 Edges with own identity: Edges are primitive entities just like nodes. When multiple
edges connect two nodes, these are different edges.
A multigraph is different from a hypergraph, which is a graph in which an edge can connect
any number of nodes, not just two.

Fig: A Multigraph with Multiple Edges (Red) and =Several Loops (Blue)
For some authors, the terms pseudograph and multigraph are synonymous. For others, a
pseudograph is a multigraph that is permitted to have loops.

70
4.2.1 Definitions

An undirected graph 𝐺 consists of:

1. A finite non-empty set of vertices 𝑉.

2. A finite set of edges 𝐸.
3. A function 𝛿: 𝐸 ⟶ (𝑉) such that for every edge 𝑒 ∈ 𝐸, 𝛿(𝑒) is a one or two-
element subset of 𝑉.

The edge 𝑒 is said to join the elements of (𝑒).

Unfortunately, there are numerous ways to define a graph. Some writers employ a definition
that forbids the existence of multiple edges in their graphs, i.e., several edges forming a
connection between the same pair of vertices. Other definitions rule out the notion of loops,
which are edges connecting one vertex to another. A graph that complies with both of these
requirements—that it be free of loops and many edges—is referred to as a simple graph.
Graph theory uses vocabulary that is clearly non-standard. It is strongly encouraged that you
carefully review the meanings and terminology used by the author while reviewing other
texts.
The degree of a vertex is the number of edges connecting it.
If an edge 𝑒 connects two vertices 𝑣 and 𝑤, they are said to be adjacent. In this instance, we
can argue that 𝑒 is incident to 𝑣 and 𝑤 as well as 𝑣 and 𝑤 to 𝑒.
The edges are adjacent if they have at least one vertex in common.
The number of edges that are incident to a vertex (𝑑𝑒(𝑣)) determines its degree or valency.
(Unless specified otherwise, a loop adding 𝑣 to itself counts as adding two to 𝑣.)
Regular (with degree 𝑟), often known as 𝒓-regular, is a graph in which every vertex has the
same degree 𝑟.

4.2.2 Subgraphs

A graph 𝐺′(𝑉′, 𝐸′) is a subgraph of a graph 𝐺(𝑉, 𝐸) if

1. 𝑉′ ⊆ 𝑉
2. 𝐸′ ⊆ 𝐸 𝖠 [(𝑣1, 𝑣2) ∈ 𝐸′ ⟶ 𝑣1, 𝑣2 ∈ 𝑉′]

In general, a subgraph does not have to have every edge that could exist. A subgraph is said
to be induced subgraph if every edge is present.

4.2.3 Isomorphic and Homeomorphic Graphs

Isomorphism testing determines whether two graph descriptions genuinely specify graphs
with the same structural properties. Only for specific unique types of graphs are polynomial-

71
time isomorphism testing techniques known. To assess the isomorphism of reasonable-sized
networks, there are heuristic techniques. Reconstructing a graph from its vertex-deleted
subgraphs is a related but unsolved topic.

If two graphs 𝐺 and 𝐻 contain the same number of vertices connected in the same way, they
are called isomorphic graphs (denoted by 𝐺 ≅ 𝐻).
It is easier to check non-isomorphism than isomorphism. If any of these following conditions
occurs, then two graphs are non-isomorphic:
 The number of connected components is different
 Vertex-set cardinalities are different
 Edge-set cardinalities are different
 Degree sequences are different

Isomorphism Principle
To show that two graphs are isomorphic, an isomorphism from one to the other must be
found; to show that two graphs are not isomorphic a graph theoretic property must be found
which one graph has but the other does not.
An elementary subdivision basically involves adding a node to an existing edge.
When two graphs can be created from one another by inserting vertices along the edges of
either one or both of the graphs, that graph is said to be homeomorphic.
Notice that every graph is homeomorphic to itself.
A complete graph is a graph in which every pair of vertices is adjacent. The complete graph
with n vertices is denoted 𝐾𝑛.
If 𝐻 is a subgraph of 𝐺, then 𝐺 − 𝐻 refers to the subgraph of 𝐺those results from subtracting
(𝐻) from 𝑉(𝐺) and eliminating all of 𝐺′𝑠 edges with endpoints in 𝑉(𝐻).

4.2.4 Paths and Connectivity

A walk is a collection of a graph's vertices and edges, therefore if we traverse a graph, we get
a walk. Note: Vertices and Edges can be repeated.
If the origin vertex and terminal vertex of a walk are distinct from one another, the walk is said
to be an open walk.
If the starting and finishing vertices of a walk are the same, or if a walk begins and finishes at
the same vertex, then it is said to be a closed walk.
Trail is an open walk in which no edge is repeated but Vertex can be repeated.
Traversing a graph in such a way that a vertex can be repeated but not an edge, is known as
closed trail.

72
Path
It is a trail in which neither vertices nor edges are repeated i.e., if we traverse a graph such
that we do not repeat a vertex and nor we repeat an edge. As path is also a trail, thus it is also
an open walk.
Note: Vertices and Edges cannot be repeated.
Cycle
Traversing a graph such that we do not repeat a vertex nor we repeat an edge but the starting
and ending vertex must be same i.e., we can repeat starting and ending vertex only then we
get a cycle.
Note: Vertices and Edges cannot be repeated.
Connectivity
If there is a path connecting every pair of vertices, a graph is said to be connected. There
should be some way to travel some path from any vertex to every vertex. That is referred to
as a graph's connectedness. A graph is considered disconnected if it has numerous
disconnected edges and vertices.
The notion of graph connectedness is crucial for network applications such as transportation
network routing and network tolerance. We frequently want to locate separation edges and
vertices because they represent single sites of failure in a network. We will primarily examine
2-connected and infrequently 3-connected graphs.
Looking at how difficult it is to disconnect a graph by eliminating vertices or edges is the
simplest method. We presume that all graphs are straightforward. A graph is said to have
connectivity 1 if it is possible to disconnect it by deleting a single vertex, or cut-point. If two
vertices can be removed from the graph to make it disconnected but this is not practicable,
the graph has connectivity 2.
Vertex Connectivity
The connectivity (or vertex connectivity) (𝐺) of a connected graph G (other than a
complete graph) is the minimum number of vertices whose removal disconnects G.
When(𝐺) ≥ 𝑘, the graph is said to be k-connected (or k-vertex connected). When we
remove a vertex, we must also remove the edges incident to it.
Edge Connectivity
If 𝐺 is a linked graph, then. If 𝐺 − 𝑒 leads to a disconnected graph, the edge 𝑒 ∈ 𝐺 is referred
to as a cut edge. An edge is referred to be a Cut Edge if removing it from a graph causes the
creation of two or more graphs.

If 𝐺 is a connected graph, then Edge connectivity of 𝐺 is the minimal number of edges

required to disconnect the graph 𝐺.

73
A graph with connectivity based on edges is more stable than one with connectivity based on
vertex. Because each vertex in a linked graph can be connected to one or more edges, this
occurs. The removal of that vertex and all of these attached edges has the same result. As a
result, a graph with one linked edge also has one connected vertex.

4.2.5 Traversable and Eulerian Graphs

If you can construct a path between every vertex of a graph without taking the same route
twice, then the graph is traversable.
Konigsberg Bridge Problem:
The Russian town of Konigsberg is traversed by the Pregel River. Figure 3.3 illustrates how
two islands in the river are connected to the banks and to one another by bridges. The
question for the Konigsberg residents was whether there existed a path that started on one of
the banks or islands, passed under each bridge exactly once, and ended back where it had
begun. They were unable to locate such a stroll; the challenge was to either locate such a
walk or demonstrate that there was none.

Fig:3.3: Pregel River

Fig : Euler Geographical Visualization

Figure 3.4 shows how Euler first visualized the key elements of Konigsberg’s geography as a
graph. Each river bank and island are represented by a vertex, with the connecting bridges

74
acting as the edges. In terms of graph theory, the question is whether a closed path that includes
every edge in the graph exists.
Euler's path
Each vertex of G appears at least once and each edge of G appears exactly once in aEuler's
path. If a Euler's path exists, a connected graph 𝐺 is said to be traversable.
Euler’s circuit
Every edge of a graph is used precisely once in a Euler circuit. At the same vertex, a Euler
circuit always begins and ends. A connected graph G is a Euler graph if and only if its edges
can be broken down into cycles, and a connected graph G is Eulerian if and only if all of its
vertices are of even degree.
Euler Graph
A connected graph G is called a Euler graph, if there is a closed trail which includes every edge
of the graph G.
Euler’s Circuit Theorem
If and only if the connected graph 𝐺 has exactly 2 or 0 odd-degree vertices, then the graph is
traversable. If a connected graph 𝐺 has exactly two vertices with an odd degree, it can include
a Euler's path but not a Euler's circuit.

4.2.6 Labeled and Weighted Graphs

Labeled Graph
If the edges or vertices of graph 𝐺 have data of one type or another allocated to them, the graph
is said to be labelled. A graph 𝐺 is specifically referred to be a weighted graph if each of its
edges (𝑒) is given a non-negative number (positive real number) that represents the weight.
Weighted Graph
A graph containing edges identified by integers (referred to as weights) is a weighted graph.
We often just take nonnegative edge weights into account. In some cases, the symbol can also
be used as a weight, which in optimization issues usually indicates we have to use that edge
(or not).

4.2.7 Complete, Regular, and Bipartite Graphs

Complete Graph
A simple graph of 𝑛 vertices having exactly one edge between each pair of vertices is called a
complete graph. A complete graph of 𝑛 vertices is denoted by𝐾𝑛. Total number of edges are
(𝑛−1) with 𝑛 vertices in complete graph.
2

75
Regular Graph
If the degree of each vertex is equal, a graph is said to be a regular graph. If the degree ofeach
vertex is 𝑘, a graph is said to be 𝑘 regular.
Properties of Regular Graph

 A complete graph on 𝑁 vertices is (𝑁 − 1) regular.

 For a 𝑘 Regular graph, if 𝑘 is odd, then the number of vertices of the graph must beeven.
[Link] A Cycle graph is always 2-Regular.
[Link] 2-Regular graphs consist of Disjoint union of cycles and Infinite Chains.
𝑁∗𝐾
[Link] Number of edges of a 𝑘-Regular graph with 𝑁 vertices = .
2

Bipartite Graph
If the vertex-set of a graph 𝐺 can be split into two disjoint sets, 𝑉1 and 𝑉2, in such a way that each
edge in the graph joins a vertex in 𝑉1 to a vertex in 𝑉2, and there are no edges in 𝐺 that connect
two vertices in 𝑉1 or two vertices in 𝑉2 , then the graph 𝐺 is called a bipartite graph. A complete
bipartite graph is a bipartite graph in which each vertex in the first set is joined toevery single
vertex in the second set. The complete bipartite graph is denoted by 𝐾𝑥, wherethe graph 𝐺
contains 𝑥 vertices in the first set and 𝑦 vertices in the second set.

4.2.8 Graph Colorings

A graph's vertex set can be colored to differentiate between adjacent vertices. Similar to this, edges
in a graph without self-loops can be colored in a way that distinguishes between adjacent edges. The
regions can be colored so that adjacent regions receive distinct colors if a graph is embedded in a
surface without any self-adjacent regions. Numerous significant applications, such as issues with
assignments and scheduling, might be made from these amusing principles. Here, we take into
account these and associated issues.
Proper Colorings
A graph is properly colored when its vertices are given different colors, ensuring that no two
neighboring vertices have the same color.
Except as otherwise specified, we presume graphs are connected; nevertheless, if a graph is
connected, each connected component can be colored individually. In this section, we also assume
that graphs are simple.
Chromatic Number
The chromatic number of a graph 𝐺 is the minimum number of colors required in a proper
coloring; it is denoted by (𝐺).
If 𝑣 and 𝑤 are different colors in a correct coloring of 𝐺, then 𝐺 + 𝑒 is also properly colored using
this coloring scheme. A valid coloring of 𝐺 that has various colors for 𝑣 and 𝑤 is any correct
coloring of 𝐺 + 𝑒. In other words, (𝐺 + 𝑒) is the smallest number of colors required to color 𝐺 so
that 𝑣 and 𝑤 have distinct colors. Therefore, coloring 𝐺 + 𝑒 with the fewest number of colors is the
optimal coloring of 𝐺 in which 𝑣 and 𝑤 have separate colors.

4.3 Planar Graphs

A graph is said to be embeddable in the plane, or planar, if it can be drawn in the plane so
that its edges intersect, only at their ends. Such a drawing of a planar graph G is called a
planar embedding of G. A planar embedding G of G can itself be regarded as a graph
isomorphic to G; the vertex set of G is the set of points representing vertices of G, the edge
set of G is the set of lines representing edges of G, and a vertex of 𝐺 is incident with all the
edges of G that contain it. We therefore sometimes refer to a planar embedding of a planar
graph as a plane graph. Figure 4.4 b shows a planar embedding of the planar graph in figure.
It is clear from the above definition that the study of planar graphs necessarily involves
the topology of the plane. However, we shall not a~tempt here to be strictly rigorous in
topological matters, and will be content to adopt a naive point of view toward them. This is
done so as not to obscure the combinatorial aspect of the theory, which is our main interest.
The results of topology that are especially relevant in the study of planar graphs are those
which deal with Jordan curves. (A Jordan curve is a continuous ,non-self-intersecting curve
whose origin and terminus coincide.) The union of the edges in a cycle of a plane graph
constitutes a Jordan curve; this is the reason why properties of Jordan curves come into
play in planar graph theory. We shall recall a well-known theorem about Jordan curves and
use it to demonstrate the nonplanarity of K5.
Let J be a Jordan curve in the plane. Then the rest of the plane is partitioned into two
disjoint open sets ~alled the interior ,al\.d exterior of J. We shall denote the interior and
exterior of J, respectively, by int J and ext J, and their closures by Int J and Ext J. Clearly Int
J ∩ Ext J =J. The Jordan curve theoremstates that any line joining a point in int J to a point in
ext J must meet J in some point (see figure 4.4-2). Although this theorem is intuitively
obvious, a formalproof of it is quite difficult.

Theorem
K5 is nonplanar
Proof
By contradiction. If possible let G be a plane graph corresponding to K5 Denote the vertices
of G by V1, V2, V3, V4 and V5. Since G is complete, any two of its vertices are joined by an
edge. Now the cycle C = V1 V2V3Vl is a Jordan, curve in the plane, and the point V4 must lie
either in, int C or ext C.

We shall suppose that V4 intC. (The case where V4 ext C can be dealt with in a similar
manner.) Then the edges V4Vl, V4V2 and V4V3 divide int C into the three regions int C1,
int C2 and int C3, where C1 = V1 V4V 2V1, C2 = V2V4V3V2 and C3 =V3V4V1V3 (see figure
9.3).

Now V 5 must lie in one of the four regions ext C, int C1, int C2 and int C3. If V5 ext C

then, since V4 int C, it follows from the Jordan curve theorem that' the edge V 4V5 must
meet C in some point. But this contradicts the assumption that G is a plane graph.
The'cases

V5 intCi, i =1, 2, 3, can be disposed of in like manner

Fig.4.4-1

Fig.4.4-2
 Fig.4.4-3

A similar argumentcan be used to establish that K3,3, too, is nonplanar. On the other hand,
every nonplanar graph contains a subdivision of either K5 orK3,3.
The notion of a planar embedding. extends to other, surfaces.t A graph G is said to be
embeddable on a surface S if it can be drawn in S so that itsedges intersect only at their ends;
such a drawing (if one exists) is called an embedding of G on S. Figure 4.4-4a shows an
embedding of K5 on the torus, and figure 4.4-4b an embedding of K3,3 on the Mobius
band.

4.3.2 TREES AND PROPERTIES OF TREES

Definition: A graph having no cycles is said to be acyclic. A forest is an acyclic graph.

Definition: A tree is a connected graph without any cycles, or a tree is a connected acyclic graph.
The edges of a tree are called branches. It follows immediately from the definition that a tree has
to be a simple graph (because self-loops and parallel edges both form cycles). Figure
[Link] displays all trees with fewer than six vertices

Fig 4.3.1

Properties of Trees:
The following result characteristics of trees.

Theorem1: A graph is a tree if and only if there is exactly one path between every pair
of its vertices.

Proof :
Let G be a graph and let there be exactly one path between every pair of vertices in G. So G is
connected. Now G has no cycles, because if G contains a cycle, say between vertices u and v, then
there are two distinct paths between u and v, which is a contradiction.
Thus G is connected and is without cycles, therefore it is a tree. Conversely, let G be a tree.
Since G is connected, there is at least one path between every pair of vertices in G. Let there be
two distinct paths between two vertices u and v of G. The union of these two paths contains a
cycle which contradicts the fact that G is a tree.
Hence there is exactly one path between every pair of vertices of a tree. q
The next two results give alternative methods for defining trees.

Theorem 2: A tree with n vertices has n−1 edges.

Proof: We prove the result by using induction on n, the number of vertices. The result is
obviously true for n = 1, 2 and 3. Let the result be true for all trees with fewer than n vertices. Let T
be a tree with n vertices and let e be an edge with end vertices u and v. So the only path between u
and v is e. Therefore deletion of e from T disconnects T. Now, T −e consists ofexactly two
components T1 and T2 say, and as there were no cycles to begin with, each component is a tree.
Let n1 and n2 be the number of vertices in T1 and T2 respectively, so that n1 +n2 = n. Also, n1 <
n and n2 < n. Thus, by induction hypothesis, number of edges in T1 and T2 are respectively n1−1
and n2−1. Hence the number of edges in T = n1−1+n2−1+1 = n1+n2−1 =n−1. Q

Theorem 3 Any connected graph with n vertices and n−1 edges is a tree.
Proof: Let G be a connected graph with n vertices and n −1 edges. We show that G contains no
cycles. Assume to the contrary that G contains cycles. Remove an edge from a cycle so that the
resulting graph is again connected. Continue this process of removing one edge from one cycle at a
time till the resulting graph H is a tree. As H has n vertices, so number of edges in H is n−1.

Now, the number of edges in G is greater than the number of edges in H. So n−1 > n−1, which is
not possible. Hence, G has no cycles and therefore is a tree. q
The torus is represented as a rectangle in which opposite sides are identified, and the
Mobius band as a rectangle whose two ends are identified after one half-twist.
We have seen that not all graphs can be embedded in the plane; this is also true of other
surfaces. It can be shown (see, for example, Frechet and Fan, 1967) that, for every
surface S, there exist graphs which are .not embeddable on S. Every graph can,
however, be 'embedded' in 3-dimensional space 𝑅3

Figure 4.4-4. (a) An embedding of Ks on the torus; (b) an embedding of K3,3 on the
Mobius band

4.3.3 SPANNING TREES

A tree is said to be a spanning tree of a connected graph G, if T is a sub graph of G

and Tcontains all vertices of G.
Example: Consider the graph of Fig. 3.8.1 where the bold lines represent a spanning tree

Fig. 4.3.2

An edge in a spanning tree T is called a branch of T. An edge of G that is not in a

given spanning tree T is called a chord. It may be noted that branches and chords are defined
only with respect to a given spanning tree. An edge that is a branch of one spanning tree T1
(in a graph G) may be a chord with respect to another spanning tree T2. In Figure 3.8.2,
u1u2u3u4u5u6 is a spanning tree, u2u4 and u4u6 are chords.

Fig. 4.3.3

A connected graph G can be considered as a union of two sub graphs T and 𝑇̅, that
is

𝐺 = 𝑇 𝖴 𝑇̅, where T is a spanning tree, 𝑇̅is the complement of T in G. T being the set
of chords is called the co tree, or chord set.

Let G be a graph with n vertices, m edges and k components. The rank r and nullity µ
of G are defined as r = n−k and µ = m−n+k. Clearly, the rank of a connected graph is n−1
and the nullity is m−n+1. It can be seen that rank of G = number of branches in any spanning
tree (or forest) of G. Also, nullity of G = number of chords in G. So, rank + nullity = number
of edges in
G. The nullity of a graph is also called its cyclomatic number, or first Betti
number. The complexity τ(G) of a graph G is the number of different spanning
trees of G

Properties of Spanning Trees:

 Every connected graph has at least one spanning tree.

 With respect to any of its spanning trees, a connected graph of n vertices and m edges
hasn−1 tree branches and m−n+1 chords.

 If T is a tree with 2k ≥ 0 vertices of odd degree, then E(T) is the union of k pair-wise
edge-disjoint paths.
 Let T be a non-trivial tree with the vertex set S and |S|= 2k, k ≥ 1. Then there exists a set
of kpairwise edge-disjoint paths whose end vertices are all the vertices of S.

 If u is a vertex of an n-vertex tree T, then

 Let v be any vertex of a connected graph G. Then G has a spanning tree preserving
thedistances from v.

 Let G be a connected graph with d = 2r, which has a unique isometric tree. Then the
end vertices of every diametral path of G has degree 1.

 For any cyclic edge e of a graph G, (𝐺) = 𝑟(𝐺 − 𝑒) + 𝑟(𝐺|𝑝𝑒).

4.4SUMMARY

 Graph theory uses vocabulary that is clearly non-standard. It is strongly encouraged

that you carefully review the meanings and terminology used by the author while
reviewing other texts.

 The degree of a vertex is the number of edges connecting it.

 If an edge e connects two vertices v and w, they are said to be adjacent. In this
instance, we can argue that e is incident to v and w as well as v and w to e.
 The edges are adjacent if they have at least one vertex in common.
 A subgraph does not have to have every edge that could exist. A subgraph is said to
be induced subgraph if every edge is present.
 If two graphs G and H contain the same number of vertices connected in the same
way, they are called isomorphic graphs
 A walk is a collection of a graph's vertices and edges, therefore if we traverse a graph,
we get a walk. Note: Vertices and Edges can be repeated.
 If you can construct a path between every vertex of a graph without taking the same
route twice, then the graph is traversable.
 A graph's vertex set can be colored to differentiate between adjacent vertices. Similar
to this, edges in a graph without self-loops can be colored in a way that distinguishes
between adjacent edges.
 By employing the adjacency matrix of a weighted directed graph, Warshall's approach
can be used to find the transitive closure of a directed network or all of its paths.
 4.5KEYWORDS

 Bag: One of the sets of vertices in a tree decomposition.

 Balanced: A bipartite or multipartite graph is balanced if each two subsets of its
vertex partition have sizes within one of each other.
 Child: In a rooted tree, a child of a vertex v is a neighbor of v along an outgoing edge,
one that is directed away from the root.
 Cone: A graph that contains a universal vertex.
 Connect: Cause to be connected.
 Direct predecessor: The tail of a directed edge whose head is the given vertex.
 Direct successor: The head of a directed edge whose tail is the given vertex.
 Directed: A directed graph is one in which the edges have a distinguished direction,
from one vertex to another.[2] In a mixed graph, a directed edge is again one that has
a distinguished direction; directed edges may also be called arcs or arrows.
 Distance: The distance between any two vertices in a graph is the length of the
shortest path having the two vertices as its endpoints.
 Edge: An edge is (together with vertices) one of the two basic units out of which
graphs are constructed.
 Forest: A forest is an undirected graph without cycles (a disjoint union of unrooted
trees), or a directed graph formed as a disjoint union of rooted trees.
 Greedy: Produced by a greedy algorithm. For instance, a greedy coloring of a graph is
a coloring produced by considering the vertices in some sequence and assigning each
vertex the first available color.

4.6LEARNING ACTIVITY

1. Define isomorphism.

2. Define a graph and a subgraph

 4.7UNIT END QUESTIONS

A. Descriptive Questions
Short Questions:

1. Explain complement of a graph

2. What do you mean by isomorphic graphs? Explain with the help of example?
3. List some ways of representing Graphs.
4. What is the largest number of vertices in a graph with 35 edges if all vertices are
of degree at least 3?"
5. What is difference between BFS and Dijkstra's algorithms when looking for
shortest path?

Long Questions:

1. Explain the BSF (Breadth First Search) traversing method in brief.

2. Explain with an example Traversable and Eulerian Graphs
3. What is meant by Isomorphic and Homeomorphic Graphs?
4. Explain Complete, Regular, and Bipartite Graphs
5. What is Warshall’s Algorithm?

B. Multiple Choice Questions

1. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be

a. 728
b. 450
c. 360
d. 260

2. Berge graph is similar to due to strong perfect graph theorem.

a. line graph
b. perfect graph
c. bar graph
d. triangle free graph
 3. Triangle free graphs have the property of clique number is
a. less than 2
b. equal to 2
c. greater than 3
d. more than 10

4. If each and every vertex in G has degree at most 23 then G can have a vertex
colouring of
a. 4
b. 23
c. 176
d. 54

5. A is a graph which has the same number of edges as its complement must
have number of vertices congruent to 4m or 4m modulo 4(for integral values of
number of edges).
e. Subgraph
f. Hamiltonian graph
g. Euler graph
h. Self-complementary graph
Answers
1-c, 2-b, 3-d, 4-a, 5-d

4.8REFERENCES

Reference Books
 Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. ISBN 0-07-005489-4.
 Bollobás, Béla (2002). Modern Graph Theory. Graduate Texts in Mathematics. Vol.
184. Springer. ISBN 0-387-98488-7.
 Chartrand, Gary; Zhang, Ping (2012). A First Course in Graph Theory. Dover. ISBN
978-0-486-48368-9.
 Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. Vol. 173
(4th ed.). Springer. ISBN 978-3-642-14278-9.
 Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC
Press. ISBN 0-8493-3982-0.
  Gross, Jonathan L.; Yellen, Jay, eds. (2003). Handbook of Graph Theory. CRC. ISBN
1-58488-090-2..

Textbook
 Hariri, Frank (1995). Graph Theory. Addison Wesley. ISBN 0-201-41033-8.
 Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris (1993). "The birth of
the giant component". Random Structures and Algorithms. 4 (3): 231–358.
arXiv:math/9310236. Bibcode:1993math.. 10236J. doi:10.1002/rsa.3240040303.
ISSN 1042-9832. MR 1220220. S2CID 206454812.
 Wilson, Robert A. (2002). Graphs, Colourings and the Four-Colour Theorem. Oxford
Science Publ. ISBN 0-19-851062-4.
 Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st
ed.). Chapman & Hall/CRC. ISBN 1-58488-291-3.
 H.J. Bernardin, Human Resource Management, Tata McGraw Hill, New Delhi, 2004

Website
 [Link]
algorithms/tutorial/
 [Link]
 [Link]