1

Graph Theory

Basic Concepts

A graph G is a pair of sets (V,E), where V is a set of vertices and E is a set of edge.
Graph with no loops is said to be simple or loop-free.
If G is finite, | V(G) | denotes the number of vertices in G, and is called the order of G
and E(G)denotes the number of edges in G, and is called the size of G.
If one allows more than one edge to join a pair of vertices, the result is then called a
multigraph.

Graph Order Size

G Non Simple Graph 4 6
G1
Simple Graph 4 5
G11
Multigraph 4 7
G111 Symmetric Directed Graph. 4

In a directed graph an edge (u,v) is said to be incident from u, and to be incident to v.

Within a particular graph, the number of edges incident to a vertex is called the in-degree
of the vertex and the number of edges incident from it is called its out-degree.
The degree of a vertex is determined by counting each loop incident on it twice and each
other edge once.
A vertex of degree zero is called an isolated vertex.
If there is an edge incident from u to v or incident on u and v, then u and v are said to
be adjacent or to be neighbors.

Graph Theory Discrete Structures Vnktrmnb

 2

The minimum of all the degrees of the vertices of a graph G is denoted by (G), and the
maximum of all the degrees of the vertices of G is denoted by (G).
If  (G) = (G) = k, that is, if each vertex of G has degree k, then G is said to be k-
regular or regular of degree k. Usually, a 3-regular graph is called a cubic graph.
The vertex c of the graph G has degree 5 while the degree of c in G1 is 3. The degree
sequence of G is (2,2,3,5) while the degree sequence of G1 is (2,2,3,3).

If V = {v1,v2,v3….vn } is the vertex set of a non directed graph G, then

If G is a directed graph, then

In any non directed graph there is an even number of vertices of odd degree
If k = (G) is the minimum degree of all the vertices of a non directed graph G, then

In particular, if G is a k-regular graph, then

? Is there a graph with degree sequence (1,3,3,3,5,6,6)?No

In a non directed graph G a sequence P of zero or more edges of the form

{v0,v1 },{v1,v2}{v2,v3 }…{vn-1,vn}is called a path from v0 to vn; v0 is the initial vertex and vn is
the terminal vertex, and they both are called endpoints of the path P.

In the definition of path, vertices and edges may be repeated. In fact, if v0 = vn, then P is
called a closed path. But ,on the other hand, if v0  vn then P is an open path.

P may have no edges at all, in which case, the length of P is zero,P is called a trivial path,
and V(P) is just the singletonset{v0}.
Path P is simple if all edges and vertices on the path are distinct except possibly the
endpoints.

Graph Theory Discrete Structures Vnktrmnb

 3

An open simple path of length n has n + 1distinct vertices and n distinct edges, while a
closed simple path of length n has n distinct vertices and n distinct edges.
The trivial path is taken to be a simple closed path of length zero.
Path of length > 1with no repeated edges and whose endpoints are equal is called a
circuit.
A circuit may have repeated vertices other than the endpoints; A cycle is a circuit with no
other repeated vertices except its end points.Thus,a cycle is a simple circuit, and, in
particular, a loop is a cycle of length1.Of course, in a graph a cycle that is not a loop
must have length at least 3, but there may be cycles of length 2 in a multigraph.

Two paths in a graph are said to be edge-disjoint if they share no common edges; they
are vertex-disjoint if they share no, common vertices.

An edge labeling of a graph G is a function f: E(G)D, where D is some domain of

labels. A vertex labeling of G is a function f:V(G)D.

Graph Theory Discrete Structures Vnktrmnb

 4

Isomorphism And Sub graphs

Two graphs G and G1 are isomorphic if there is a function f:V(G)V(G1) from the
vertices of G to the vertices of G1 such that
(i) f is one-to-one,
(ii)f is onto,and
(iii) for each pair of vertices u and v of G,{u,v}E(G) iff {f(u),f(v)}E(G1).

The condition (iii) says that vertices u and v are adjacent in G iff f(u) and f(v) are
adjacent in G'. In other words, we say that the function f preserves adjacency.

If the graphs G and G1 are isomorphic and f is an isomorphism of G to G1, then

intuitively the only difference between the graphs is the names of the vertices. Indeed, if
we were to change the names of the vertices of G1 from f(v) to v for each v  V(G),
then G1 with the newly named vertices would be identical to the graph G, for then they
both would have the same lists of vertices and edges.

if G and G1 are isomorphic graphs the isomorphism f is by no means unique, there may
be several isomorphisms from G to G1 But if such an isomorphism f exists, then there are
several conclusions we can make, namely,
1. |V(G)|=|V(G')|
2. E(G)=E(G1)
3. If v V(G) , then degG(v)= degG(f(v)) and, thus, the degree sequences of G and G1 are
the same.

If {v,v} is a loop in Gthen{f(v),f(v)} is a loop in G1 ,and more generally if

v0-v1-v2....vk-1-vk =v0 is a cycle of length k in G, the f( v0)-f(v1 )-f(v2)....f(vk-1)-f(vk) is a cycle
of length k in G1 .

In particular, the cycle vectors of G and G1 are equal, where the cycle vector of G is by
definition the vector (c1 ,c2… cn) where ci is the number of cycles in G of length i. Of
course, c1 = 0 for simple graphs and c2 is nonzero only for multigraphs.

Discovering Isomorphism

v1,v2....vn are the vertices of G, then the adjacency matrix for this ordering of the vertices
of G is the n x n matrix A, where the ij th entry (i,j) of A is 1 iff the edge {vi,vj} is an edge
of G; otherwise, A (i,j) = 0.

A is a symmetric matrix each of whose entries is either 0 or 1.Moreover, 1 will appear on

the ith position of the diagonal of A iff there is a loop at vi. Of course, if we change the
ordering of the vertices of G, then the entries of A will be rearranged.

Graph Theory Discrete Structures Vnktrmnb

 5

Suppose that G and G' are two graphs and that f: V(G)V(G1) is a one-to-one onto
function. Let A be the adjacency matrix for the vertex ordering v1,v2…. vn.of the vertices
of G.

Let A' be the adjacency matrix for the vertex ordering f( v1),f(v2)..f(vn) . Then f is an
isomorphism from V(G) to V(G') iff the adjacency matrices A and A' are equal.

In this case, both of these maps are isomorphisms. For instance, we can verify that the
map f which maps a to c', b to b', c to a' , d to d', and e to e' is an isomorphism because
the adjacency matrix for G for the ordering a,b,c,d,e and the adjacency
matrix for G' for the ordering f(a) = c',f(b)= b' f(c) = a', f(d) = d',f(e) = e' is the matrix.

If G and H are graphs then if is a subgraph of G iff V(H) is a subset of V(G) and E(H) is a
subset of E(G).

A subgraph H of G is called a spanning subgraph of G iff V(H) = V(G).

If W is any subset of V(G),then the subgraph induced by W is the subgraph H of G

obtained by taking V(H) = W and E(H) to be those edges of G that join pairs of vertices
in W.

Graph Theory Discrete Structures Vnktrmnb

 6

A simple non directed graph with n mutually adjacent vertices is called a complete graph
on n vertices, and may be represented by the symbol kn.

A complete graph on n verticeshas n (n-1)/2 edges, and each of its vertices has degree n-1.

A complete subgraph on two vertices,K2,is just two vertices joined by an edge.

Any graph may be viewed as made up of "building blocks" which are complete
subgraphs.

For example,both graphs in the following consist of two K3 graphs joined at a common
edge, a K2 graph, and a loop.

Graph Theory Discrete Structures Vnktrmnb

 7

Complement of the Graph

If if is a sub graph of G, the complement of H in G,denoted by Hc(G), is the sub

graph G - E(H);that is, the edges of H are deleted from those of G. If H is a simple graph
with n vertices the complement Hc of H is the complement in Kn

Graph Theory Discrete Structures Vnktrmnb

 8

It follows from this definition that V(Hc) = V(H) and any two vertices are adjacent in Hc
if and only if they are not adjacent in H. Note that the degree of a vertex in Hc plus its
degree in H is n - 1,where n = |V(H).

Graph Theory Discrete Structures Vnktrmnb

 9

Intersection & Union

Let G and G' be two graphs. The intersection of G and G1 written G  G1 is the graph
whose vertex set is V(G)  V(G1) and whose edge set is E(G) E(G').
Similarly, the union of G and G1 is the graph with vertex set V(G)  V(G1) and edge set
E(G)  E(G1).
In general, if G is a simple graph with n vertices, then G  G1 is a complete graph on n
vertices.

Special Graphs

A cycle graph of order n is a connected graph whose edges form a cycle of length n.
Cycle graphs are denoted by Cn.

A wheel of order n is a graph obtained by joining a single new vertex (the "hub") to each
vertex of a cycle graph of order n - 1. Wheels of order n are denoted by Wn.

A path graph of order n is obtained by removing an edge from a C n graph. Path graphs
of order n are denoted by Pn.

A null graph of order n is a graph with n vertices and no edges.

Null graphs of order n are denoted by Nn.
(Note that this is in contrast to the empty graph, which has no vertices and no edges.)

Graph Theory Discrete Structures Vnktrmnb

 10

Figure Description
a K5
b C5
c W5
d P5
e N5

A bipartite graph is a non directed graph whose set of vertices can be partitioned into
two sets M and N in such a way that each edge joins a vertex in M to a vertex in N.
A complete bipartite graph is a bipartite graph in which every vertex of M is adjacent to
every vertex of N.
The complete bipartite graphs that may be partitioned into sets M and N as above such
that |M= m and |N= n are denoted by Km,n (where we normally order m and n such
that m < n).

Any graph that is K1,n is called a star graph.

Figure Description
a K3,3
b K2,4
c K1,5

Graph Theory Discrete Structures Vnktrmnb

 11

Planar Graphs

Graph G is said to be planar if it can be drawn on a plane without any crossovers;

Otherwise G is said to be non planar.

a planar graph is a plane graph if it is already drawn in the plane so that no two edges
cross over.

Suppose we have three houses and three utility outlets (electricity, gas, and water)
situated so that each utility outlet is connected to each house. Is it possible to connect
each utility to each of the three houses without lines or mains crossing.

Graph Theory Discrete Structures Vnktrmnb

 12

Find a systematic way to draw a graph in the plane without edges crossing. We want to
be able to conclude that a graph is non planar if our construction fails. The method
we will use involves two simple ideas:

1. If we have drawn a cycle in the plane, then any edge not on the cycle must be either
inside the cycle, outside the cycle, or the edge must crossover one of the edges of the
cycle.
2. The roles of being inside or outside the cycle are symmetric that is,the graph can be
redrawn so that edges and vertices formerly outside the cycle are now inside the cycle
and vice versa

A plane graph G can be thought of as dividing the plane into regions or faces. Intuitively
the regions are the connected portions of the plane remaining after all the curves and
points of the plane corresponding, respectively, to edges and vertices of G have been
deleted.

Each plane graph G determines a region of infinite area called the exterior region of G.
The vertices and edges of G incident with a region r make up the Boundary of the region
r. If G is connected, then the boundary of a region r is a closed path in which each cut-
edge is traversed twice.

When the boundary contains no cut edges of G, then the boundary of r is a cycle of G.
In either case, the degree of r is the length of its boundary. Of course, a cycle of G need
not be the boundary of a region.

Graph Theory Discrete Structures Vnktrmnb

 13

Given a plane graph G, we can define another multigraph G* as follows:

Corresponding to each region r of G there is a vertex r* of G*, and corresponding to
each edge e of G there is an edge e* of G*; two vertices r* and s* are joined by the edge
e*in G* iff their corresponding regions r and s are separated by the edge e in G.
In particular, a loop is added at a vertex r* of G * for each cut-edge of G that belongs to
the boundary of the region r. The multigraph G* is called the dual of G.

Let |E*|, | R* |, | V* | and |E|, | R |, | V | denote the number of edges,regions,and

vertices of G* and G respectively.
The following relations are direct consequences of the definition of G*:

i. | E* |= | E|
ii. |V* |= | R| and
iii. DegG * (r*) = DegG (r) for each region r of G. Moreover ,if G is connected, it can
be shown that
iv. |R*|=|V|.
In (iii) we mean that the degree of the vertex r* in G* is the same as the degree of the
corresponding region r determined by G.

If G is a plane graph, then the sum of the degrees of the regions determined by
G is 2| E|, where | E| is the number of edges of G.

Graph Theory Discrete Structures Vnktrmnb

 14

Euler and Hamiltonian Graphs

Euler's Formula:If G is a connected plane graph then |V|-|E| + |R| = 2.

In a connected plane (simple) graph G, with |E| > 1,

(1) |E|<=3|V|- 6 and
(2) there is a vertex v of G such that degree (v) < 5.

A complete graph Kn is planar iff n <= 4.

A complete bipartite graph Km,n is planar iff m <= 2 or n <= 2.

Multigraphs And Euler Circuits

An Euler path in a multigraph is a path that includes each edge of the multigraph exactly
once and intersects each vertex of the multigraph at least once.
A multigraph is said to be traversable if it has an Euler path.
An Euler circuit is an Euler path whose endpoints are identical. (That is, if
an Euler path is a sequence of edges e1 ,e2….ek corresponding to the sequence of pairs of
vertices(x1,x2),(x2,x3)….,(xk-1,xk) then the then the ei’s are all distinct, and x1=xk)

A multigraph is said to be an Eulerian multigraph if it has an Euler circuit.

A non directed multigraph has an Euler path iff it is connected and has 0 or exactly 2
vertices of odd degree. In the latter case, the two vertices of odd degree are the
endpoints of every Euler path in the multigraph.

A non directed multigraph has an Euler circuit iff it is connected and all of its vertices are
of even degree.

A directed multigraph G has an Euler path iff it is unilaterally connected and the in-
degree of each vertex is equal to its out-degree, with the possible exception of two
vertices, for which it may be that the in-degree of one is one larger than its out-degree
and the in-degree of the other is one less than its out-degree.

A directed multigraph G has an Euler circuit iff G is unilaterally connected and the in-
degree of every vertex in G is equal to its out-degre.

Graph Theory Discrete Structures Vnktrmnb

 15

The problem of drawing a multigraph on paper with a pencil without lifting the pencil or
repeating any lines is clearly a problem of finding an Euler path in the multigraph.
A multigraph can be drawn in this way iff it has an Euler path.

Hamiltonian Graphs

Suppose that a traveling salesman's territory includes several cities with roads connecting
certain pairs of these cities. Suppose additionally that the salesman's job requires that he
visit each city personally. Is it possible for him to schedule a roundtrip by car enabling
him to visit each specified city exactly once.

Graph G is said to be Hamiltonian if there exists a cycle containing every vertex of G.

Such a cycle is referred to as a Hamiltonian cycle. Thus, a Hamiltonian graph is a graph
containing a Hamiltonian cycle.
We define a Hamiltonian path as a simple path that contains all vertices of G but where
the endpoints may be distinct. Since a graph is Hamiltonian iff its underlying simple graph
is Hamiltonian we limit our discussion to simple graphs.

Whereas the Euler circuit is a circuit that traverses each edge exactly once and, therefore,
traverses each vertex at least once, a Hamiltonian cycle traverses each vertex exactly
once.

A Hamiltonian cycle always provides a Hamiltonian path, upon deletion of any edge.
On the other hand, a Hamiltonian path may not lead to a Hamiltonian cycle (it depends
on whether or not the end points of the path happen to be joined by an edge in the
graph).

Some Basic Rules for Constructing Hamiltonian Paths and Cycles

Rule 1. If G has n vertices, then a Hamiltonian path must contain exactly n - 1 edges, and
a Hamiltonian cycle must contain exactly n edges.

Rule 2. If a vertex v in G has degree k, then a Hamiltonian path must contain at least one
edge incident on v and at most two edges incident on v. A Hamiltonian cycle will, of
course, contain exactly two edges incident on v. In particular, both edges incident on a
vertex of degree two will be contained in every Hamiltonian cycle. In sum: there cannot
be three or more edges incident with one vertex in a Hamiltonian cycle.

Rule 3. No cycle that does not contain all the vertices of G can be formed when building
a Hamiltonian path or cycle.

Rule 4. Once the Hamiltonian cycle we are building has passed through a vertex v, then
all other unused edges incident on v can be deleted because only two edges incident on
v can be included in a Hamiltonian cycle

Graph Theory Discrete Structures Vnktrmnb

 16

(Grinberg). Let G be a simple plane graph with n vertices. Suppose that C is a

Hamiltonian cycle in G. Then with respect to this cycle C,

Dirac's Theorem. A simple graph with n vertices (n >= 3) in which each vertex has
degree at least n/2 has a Hamiltoniancycle.

If G is a complete simple graph on n-vertices (n > =3), then G has a Hamiltonian cycle.
(is true even for directed graphs).

Chromatic Number

The Scheduling Problem

Suppose that the state legislature has a list of 21 standing committees. Each committee is
supposed to meet one hour each week. What is wanted is a weekly schedule of
committee meeting times that uses as few different hours in the week as possible so as to
maximize the time available for other legislative activities. The one constraint is that no
Legislator should be scheduled to be in two different committee meetings at the same
time. The question is: What is the minimum number of hours needed for such a schedule?

First, we model this problem with a "committee" graph G0 that has a vertex for each
committee and has an edge between vertices corresponding to committees with a
common member. But then we need to introduce a new graph theoretic concept.

By a vertex coloring of a graph G, we mean the assignment of colors (which are simply
the elements of some set) to the vertices of G, one color to each vertex, so that adjacent
vertices are assigned different colors.
An n-coloring of G is a coloring of G using n colors. If G has an n-coloring then G is said
to be n-colorable.

Graph Theory Discrete Structures Vnktrmnb

 17

The question is: What is the minimum number of colors required? We define the
chromatic number of a graph G to be the minimum number n for which there exists an
n-coloring of the vertices of G. We denote the chromatic number of G by (G), and if
(G) = k we say that G is k-chromatic.

(G)=4.

Rule 1. (G) <=V where | V is the number of vertices of G.

Rule 2. A triangle always requires three colors, that is, (K3)= 3;more generally, (Kn) =
n where Kn is the complete graph on n vertices.

Rule 3. Ifsome subgraph of G requires k colors then (G) >= k.

Rule 4. If degree (v) = d, then at most d colors are required to color the vertices
adjacent to v.

Rule 5. (G) = maximum { (C) C is a connected component of G}.

Rule 6. Every k-chromatic graph has at least k vertices v such that degree (v) >= k -1.

Graph Theory Discrete Structures Vnktrmnb

 18

Rule 7. For any graph G, (G) <= 1 + (G), where (G) is the largest degree of any
vertex of G.
Rule 8. When building a k-coloring of a graph G, we may delete all vertices of degree
less than k (along with their incident edges). In general, when attempting to build a k-
coloring of a graph, it is desirable to start by k-coloring a complete subgraph of k vertices
and then successively finding vertices adjacent to k - 1 different colors, thereby forcing the
color choice of such vertices.

Rule 9. These are equivalent:

(i) A graph G is 2-colorable.
(ii) G is bipartite,
(iii) Every cycle of G has even length.

Rule 10. If (G) is the minimum degree of any vertex of G, then

(G) > =| V|/| V| - (G) where| V | is the number of vertices of G.

A graph G to be k-critical if (G) = k and (G - v) < (G) for each vertex v of G. It is
easy to see that a k-chromatic graph has a k-critical subgraph.

The following properties of k-critical graph

(i) G is connected,
(ii) The degree of each vertex of G is at least k - 1, that is, (G) >= k -1.
(iii) G cannot be expressed in the form G1 U G2, where G1 and G2 are graphs which
intersect in a complete graph. In particular, G contains no cut vertices.

Graph Theory Discrete Structures Vnktrmnb

 19

Directed Trees

Under what conditions does a digraph have a directed spanning tree? The answer
requires us to give a characterization of directed trees and of quasi-strongly connected
graphs.

Two vertices u and v of a directed graph G are said to be quasi-strongly connected if

there is a vertex w from which there is a directed path to u and a directed path to v.

Of course, if there is a directed path P from u to v then certainly u and v are quasi-
strongly connected, because we may take w to be u itself, and then there is the trivial
path with no edges from u to u and the path P from u to v.

The graph G is said to be quasi-strongly connected if each pair of vertices of G is quasi-

strongly connected.

In the graph of Figure (a) the vertex e is special in the sense that there is a directed path
from e to every other vertex.

Let G be a digraph. Then the following are equivalent:

1. G is quasi-strongly connected.
2. There is a vertex r in G such that there is a directed path from r to all the remaining
vertices of G.

There is a directed path from wn to each vertex Vi of G since wn is connected to v1 ,v2..

vn through wn-1.

Graph Theory Discrete Structures Vnktrmnb

 20

Let G be a digraph with n > 1 vertices. Then the following statements are equivalent:

1. G is a directed tree.
2. There is a vertex r in G such that there is a unique directed path from r to every other
vertex of G.
3. G is quasi-strongly connected and G - e is not quasi-strongly connected for each edge e
of G.
4. G is quasi-strongly connected and contains a vertex r such that the in-degree of r is
zero (that is, deg+(r)= 0)and deg+(v) = 1 for each vertex v r.
5. G has no circuits (that is, G has no directed circuits and no non directed circuits) and
has a vertex r such that deg+(r)= 0and deg+(v) = 1 for each vertex v r.
6. G is quasi-strongly connected without circuits.
7. There is a vertex r such that deg+(r)= 0and deg+(v) = 1 for each vertex v r and the
underlying non directed graph of G is a tree.

A digraph G has a directed spanning tree if and only if G is quasi-strongly connected.

A directed forest is a collection of directed trees.
The height of a vertex v in a directed forest is the length of the longest directed path
from v to a leaf.
The height of a (nonempty) tree is the height of its root.
We adopt the convention that -1 is the height of the empty tree.
The level ofa vertex v in a forest is the length of the path to v from the root of the tree
to which it belongs.
A directed tree T is said to have degree k if k is the maximum of the out-degrees of all
the vertices in T.

Graph Theory Discrete Structures Vnktrmnb

 21

There are between 0 and kL vertices at level L in any directed tree of degree k.

There are between h + k and (Kh+1-1)/(k-1) vertices in a directed tree of height h and
degree k.
Complete Tree with Degree 3

A complete (directed) tree of degree k has the maximum possible number (exactly kL) of
vertices in each level, except possibly the last.

There are between (Kh+k-2)/(k-1) and (kh+1 -1)/(k-1) vertices in a complete directed tree of
degree k and height h.

A B-tree of order k, (or a k-way B-tree) is a directed tree such that:

1. all the leaves are at the same level;
2. every internal vertex, except possibly the root, has at least k/2 children.
3. the root is a leaf or has at least two children; and
4. no vertex has more than k children

(a) B-tree (b) Non B tree

A B-tree of order k and height h has at least 2 k/2h-1 leaves, for h >= 1.

Graph Theory Discrete Structures Vnktrmnb

 22

Trees and Their Properties

A tree is a simple graph G such that there is a unique simple non directed path between
each pair of vertices of G.

A rooted tree is a tree in which there is one designated vertex, called a root. A rooted
tree is a directed tree if there is a root from which there is a directed path to each vertex.

The level of a vertex v in a rooted tree is the length of the path to v from the root.
A tree T with only one vertex is called a trivial tree; otherwise T is a nontrivial tree.

A tree may be either a digraph or a non directed graph. Note that in a tree any vertex
may be designated as a root.

Two kinds of no directed trees

Two trees, G1 and G2, G1=f(V,E1) and G2 ='(V,E2), where

V=[a,b,c,d,e,f,g,h,i,j}
E1={(a,c),(b,c),(c,d),(c,e),(e,g),(f,g),(g,i),(h,i),(i,j) }
E2={(c,a),(c,b),(c,d),(c,f),(f,e),(f,i),(g,d),(h,e),(j,g)}

Neither of above trees is a directed tree. If vertex c is designated as the root of each tree,
vertex j is at level 4 in G1 and at level 3 in G2.

Graph Theory Discrete Structures Vnktrmnb

 23

Directed Tree

Trees arise in many practical applications; frequently they occur in situations where many
elements are to be organized into some sort of hierarchy that expresses what is more
important, what must be done first, or what is more desirable.

For instance, a tree can be used to show the order in which tasks are to be completed in
the assembly of some product; the root can represent the finished product, and tasks that
can be done concurrently appear on the same level, whereas if task A must ‘be
completed before task B can start, then A would have to lie on a higher level than B.

Two vertices a and b of a graph are said to be connected iff there is a non directed path
from a to b in G, and then the graph G is connected iff each pair of its vertices is
connected.

Graph Theory Discrete Structures Vnktrmnb

 24

In general, if we define the relation R on the vertices of a graph G by aRb iff a and b are
connected, then R is an equivalence relation. Consequently, the vertices of G can be
partitioned into disjoint nonempty sets V1, V2….Vk and the sub graphs H1, H2…. HK
of G induced by respectively, are called the connected components of G or simply the
components of G.(C(G)).

An undirected graph is called connected if there is path between every pair of distinct
vertices.

A graph that is not connected is the union of two or more connected sub graphs each of
which has no vertex common. These disjoint connected sub graph are called conned
components of G.

If a graph G is connected and e is an edge such that G - e is not connected, then e is said
to be a bridge or a cut edge.
If v is a vertex of G such that G-v not connected, then v is a cut vertex.

A simple non directed graph G is a tree iff G is connected and contains no cycles.
In every nontrivial tree there is at least one vertex of degree 1.(We are excluding the
trivial tree with only one vertex.)

A tree with n vertices has exactly n – 1 edges.

Graph Theory Discrete Structures Vnktrmnb

 25

If G is a nontrivial tree then G contains at least 2 vertices of degree 1.

If two non adjacent vertices of a tree T are connected by adding an edge, then the
resulting graph will contain a cycle.

A graph G is a tree if and only if G has no cycles and E=V-1

If G is a tree, then the sum of degrees equals 2V -2.

If G is a simple graph with C(G) connected components, if e is any edge of G, then G-e
at most C(G) + 1 components.
In particular if, G is a forest, than G - e has exactly C(G) + 1 components.

For a simple graph G with C(G) connected components the number of edges of G that
V(G)=C(G)+E(G).

A graph with no vertices of odd degree and no vertices of degree 0 must contain a
circuit.

G1 and G2 are isomorphic graphs , if G1 is connected, then G2is connected.

Spanning Trees

A sub graph H of a graph G is called a spanning tree of G if

(a) if is a tree, and
(b) H contains all the vertices of G.
A spanning tree that is a directed tree is called a directed spanning tree of G.

Graph Theory Discrete Structures Vnktrmnb

 26

In general, if G is a connected graph with n vertices and m edges, a spanning tree of G

must have n - 1 edges. Hence, the number of edges that must be removed before a
spanning tree is obtained m-(n-1)=m-n+1.This number is frequently called the
Circuit rank of G.

A non directed graph G is connected if and only if G contains a spanning tree. Indeed, if
we successively delete edges of cycles until no further cycles remain, then the result is a
spanning tree of G.

Graph Theory Discrete Structures Vnktrmnb

 27

Let T be a rooted tree with designated root v0.

Suppose that u and v are vertices in T and that v0-v1 -v3…-vn-1-vn is a simple path in T.
Then
(a) vn-1 is the parent of vn.
(b) v0,v1…vn-1 are the ancestors of vn.
(c) vn is a child of vn-1
(d) If u is an ancestor of v, then v is a descendant of u.
(e) If u has no children, then a is a leaf of T.
(f) If v is not a leaf of T, then v is an internal vertex of T.
(g) The subgraph of T consisting of v and all its descendants, with v designated as a root,
is the subtree of T rooted at v.

Graph Theory Discrete Structures Vnktrmnb

 28

Breadth-First Search for a Spanning Tree.

Input: A connected graph G with vertices labeled v1,v2….vn

Output: A spanning tree T for G.

Method:

1. (Start) Let v1 be the root of T. Form the set V - {v1}.

2. (Add new edges.) Consider the vertices of V in order consistent with the original
labeling. Then for each vertex x  V, add the edge {x,vk} to T where k is the minimum
index such that adding the edge {x,vk} to T does not produce a cycle.

If no edge can be added, then stop; T is a spanning tree for G.

After all the vertices of V have been considered in order, go to Step 3.

3. (Update V.) Replace V by all the children v in T of the vertices x of V where the edges
{x,v} were added in Step 2. Go back and repeat Step2 for the new set V.

Depth-First Search for a Spanning Tree.

Input: A connected graph G with vertices labeled v1,v2….vn

Output: A spanning tree T for G.

Method:

1. (Visit a vertex.) Let v1 be the root of T, and set L – v1 (The name L stands for the
vertex last visited.)

2. (Find an unexamined edge and an unvisited vertex adjacent to L.)

For all vertices adjacent to L, choose the edge{L,vk}, where k is the minimum index
suchthat adding{L,vk} to T does not create a cycle.

If no such edge exists, goto Step3;otherwise, add edge {L,vk} to T and set L = vk repeat
Step 2 at the new value for L.

3. (Backtrack or terminate.) If x is the parent of L in T, set L = x and apply Step 2 at the

new value of L. If, on the other hand, L has no parent in T (so that L = v1) then the
depth-first search terminates and T is a spanning tree for G.

Graph Theory Discrete Structures Vnktrmnb

 29

Graph Theory Discrete Structures Vnktrmnb