Chapter-2

3. Can you construct a disconnected graph G of two

or more vertices such that Complement G is also
disconnected. Give a proof supporting your answer.

Answer: No . Because two graph G and

complement G both are not simultaneously
disconnected .Either G or it’s Complement must be
connected.So I prove either G or it’s complement
graph is connected .

Proof :

Give some figures .

5. What is the necessary and sufficient condition for
K(m,n) to be a regular graph?

Answer :
In the complete bipartite graph K(m,n) , the vertices have degree m or degree n (and
both of these degrees are reached). Thus, if you want it to be regular, a sufficient and
necessary condition is n=m .

6. Is there a simple graph of n vertices such that the

vertices all have distinct degrees? Give a proof
supporting your answer.

Answer:NO .
Proof:
8. Show that two graphs are isomorphic if and only if
their complements are isomorphic.
Answer:

Figures
 Chapter- 3

Lemma 3.4.3 Let G be a k-connected graph, and let

G(prime) be obtained from G by adding a new vertex
x with at least k neighbors of G. Then G(prime) is
also k-connected.
Proof:
Let S be a separator of G(prime).We have to show |S| >= k.
Case(i) : If S contains x, then S \ {x} must be a separator of G . Since G is k -
connected then |S\{x}|>=K and so |S|>= K+1.
Case(ii):Assume now that x is not in S . If N(x) is subset of S (where N(x) is
neighbor of x) then |S|>=k.

Case(iii) : assume S does not contain x and contains at most part of N(x)
but not all the elements.
T = N(x) - S . and |T| > 0
So x is in the same component of G(prime)\S as T. So S must be a vertex
cut . |S| >= k .

Lemma 3.4.4 Let G be a connected graph and let B1

and B2 be two distinct blocks of G. Then B1 and B2
can have at most one common vertex.
ASSUME there are distinct blocks B1 and B2 of G with at least two
common vertices.Here, B1 and B2 are necessarily loopless. Because
they are distinct maximal nonseparable subgraphs of G neither one
contains the other. Hence B=B1 ∪B2 properly contains both B1.and B2.
Let v ∈V(B). Then B−v= ( B1 −v )∪(B2−v) is connected because B1−v
and B2 −v are both connected (since B1 and B2 are blocks, then they are
by definition non separable and so v is not a separating vertex and
hence is not a cut vertex) and B1−v and B2−v have at least one common
vertex by our assumption.
Since B1 and B2 are blocks, no vertex of Bi is a cut vertex of Bi for
i∈{1,2} (as just described) and hence no vertex of B is a cut vertex of B.
So B is a loopless connected graph with no cut vertices (and hence, by
Note 5.2.A, no separating vertices) so that B is nonseparable.
But this CONTRADICTS the fact that blocks B1 and B2 are maximal non
separable graphs. So the assumption that B1 and B2 have two common
vertices is false. So two blocks of G have at most one vertex in common,
as claimed.

1. Let G be a graph having exactly two vertices u

and v of degree three and all other vertices have
even degree. Then show that there is an u, v-path in
G.
Answer:
2)Write an algorithm to find a Eulerian circuit in an Eulerian graph based on
the
sufficiency proof of Lemma

(a)First,pick a vertex to the “ start vertex."

(b)Find at random a cycle that begins and ends at the start vertex.Mark all edges on
this cycle.This is now your “current circuit."
(c)If there is not a vertex on the current circuit that is incident to an unmarked edge,
you are done.If there is such a vertex,find a random cycle using unmarked edges
that begin and end at this vertex. Mark the edges in this cycle as you find it.Splice
this cycle into the current circuit to make a new, larger current circuit that begins and
ends at the start vertex. Repeat this step.

3)Lemma 3.2.2 A connected graph G is Eulerian if and only if G has

a cycle decomposition.

Proof:
Let G(V, E) be a connected graph and let G be decomposed into cycles. If k of these
cycles are incident at a particular vertex v, then d(v) = 2k. Therefore the degree of
every vertex of G is even and hence G is Eulerian.
Conversely, let G be Eulerian. We show G can be decomposed into cycles. To prove
this, we use induction on the number of edges.Since d(v) 2 for each v 2 V, G has a
cycle C. Then G−E(C) is possibly a disconnected graph, each of whose components
C1, C2, . . . , Ck is an even degree graph and hence Eulerian. By the induction
hypothesis, each Ci is a disjoint union of cycles. These together with C provide a
partition of E(G) into cycles.
5. Let Kn be a complete graph of n vertices where n is odd and
n ≥ 3. Show that Kn has (n − 1)/2 edge-disjoint Hamiltonian
cycles.
Answer:
6. Show that every k-regular graph on 2k + 1 vertices is
Hamiltonian

7. Write an algorithm to find a pair of vertex disjoint paths between

a pair of vertices in a 2-connected graph.

Answer:
Let (u,v) be such a pair of vertices .
(1) Run DFS using u as start vertices find a path of edges and marked this edge
already visited
(2) Again run DFS using u as start vertices. But this time slightly modified inside
dfs loop the edge which is marked in step one ignored that. Only pick
 unmarked ones.Hence our graph is 2 connected we find a disjoint second
path from u to v.

8. Write an algorithm to find an ear decomposition of a

biconnected graph.

Answer:
(i) Run DFS to find the first cycle. Let's P0 . Output this.
(ii) Marked all the edges on P0.
(iii) While there is at least an unmarked edge
Do
Let (u,v) be an unmarked edge on G - E(P0) . We pick this
We pick this (u,v) edge. Then using this edge apply dfs(u)
and dfs(v) to find two vertex which is on the pre-computed
Ear graph.Let applying dfs(u) we find x and applying dfs(v)
We find y . Then a path from x to y which is goes through the
edge (u,v) is our Pi . Output this Pi & marked all the edge on
Pi.
End do

10. Show that a 3-connected graph has at least six

edges.

K(G) = 3
k(G) < = K’(G)
So k’(G) > = 3
So each vertex of a 3 connected graph has at least 3 edges.
And the minimum number of vertices in a 3-connected
graph is 4 .

11)Let G be a connected graph in which there are

exactly four odd degree vertices. Prove that there are
two trails in G such that each edge of G belongs to
exactly one of these trails. [3]
 Chapter - 4

1.Show that a forest with n vertices and k components has n

− k edges.
2. Show that a forest with n vertices and m edges contains n
− m components.
3. Show that a graph with n vertices, m edges, and n − m
components is acyclic.
4.Prove the correctness of Kruskal’s algorithm described in
Section
5. Draw all labeled trees with four vertices.
6. Construct all labeled spanning trees of K4.How many of
them are non isomorphic?
9. Show that the center of a tree is a single vertex if the
diameter of the tree is even.
(1) If the diameter is even, the diameter path contains an
odd number of vertices.
(2) Diameter is always from a leaf to a different leaf.
(3) When we try to find the center of a graph, we repeatedly delete leaves
(4) if we delete the two leaves / the endpoints of the diameter, the diameter path is
always reduced by 2 vertices which leaves out the single odd vertex in the end
as the center

15. Show that every tree containing a vertex of degree k

contains at least k leaves.
 Chapter - 5

3. Write a formal proof of Theorem 5.1.4.

4. Show that every k-regular bipartite graph has a perfect

matching.
9. Let T be a tree in which every leaf is of distance 2 from another
leaf. Show that every maximum independent set of T must
contain all the leaves of T .

10. Show that a tree in which every maximal path has an even
length has a unique maximum independent set. Can you describe
the vertices of this unique set?
Claim: tree tar root jodi emon vabe neya hoy je distance to every (non-root) leaf is even,
then coloring every even level with red gives the maximum independent set, in red color
Eirokom ekta root always exist kore, e.g., jkono leaf I emon ekta root. Call this root "special
root". Jei special root ei jhulano hok, ei coloring ta same. How? Because odd level gula te
blue color dile complete bicoloring hoye jay, where every leaf is colored red. This is true for
every special root, and evidently all these bicolorings are same.So amra claim kortesi je
jkono special root dhorei even level red color korle "only" maximum independent set pawa
jay. Now we will induct on it
n=1 is trivial. (you can also check for n=3 if you want). For n>1, jkono special root, "r" e
jhulaile min depth of leaf = 2. Ekhon r er children set c_1,...,c_k.
Delete r & c_1,...,c_k from tree to get many subtrees. Jkono c_i er under e jara subtrees
ase, tader jonno maximal independent set hocche root ke and other even levels ke red
kora. Amra jodi jkono c_i er under e kono subtree er coloring change kore corresponding
root ke colorless kori, then oi subtree te independent set er size at least 1 kome, by
inductive hypothesis. Er fole highest amra c_i ke red korte pari.
1) jodi c_i ke red na kora hoy, then independent set er size (in subtree rooted at c_i) 2 kome
jay. Eki argument e onnanno c_j rooted subtree te red colored node er shongkha bare na.
Amra jodi root r keo color kori, then red colored node er shongkha at least ek kome gelo.
(compared to the coloring where every even level is colored red, odd level colorless).
2) jodi c_i ke red kora hoy, then c_i rooted subtree te red colored node er shongkha <=
reference coloring ( = every even level red colored in full tree). This can be done also in
some other c_j rooted trees. However, now we cannot color root r. So independent set er
size at least ek kome.This argument holds for every special root r. So jkono special root r e
jhulaile even level coloring gives max independent set. And for all special roots, this is the
same coloring

-
11. Show that a graph with n vertices, m edges, and n
m components are acyclic
https://math.stackexchange.com/questions/3463521/proving-the-g
eneralization-of-eulers-formula-for-a-graph-g-with-k-connected
12. A dominating set D of a graph G is an independent
dominating set if D is an independent set of G. Show that D is an
independent dominating set if and only if D is a maximal
independent set
12.
Maximal independent set nilam ekta. Node gula ke red color dei. Tar mane eikhane r notun
kono node add kora jay na. Tar mane uncolored node gular adjacent red color node nawa
hoise. So eita dominating set o
Eita sufficiency

Ekhon ekta independent dominating set niye node gula red color kori. Eita ekta independent
set. Kintu eita dominating set o. Tar mane uncolored node gular adjacent node gula colored
Eita necessity
13. Prove or disprove: if a tree has a 1-factor, then the 1-factor is
unique

.
.
 Chapter - 6

1.Show that Petersen graph is nonplanar

2.
3. Show that m < 2n- 4 for a planar bipartite graph of
n vertices and m edges.

7. Show that the dual graph of a maximal plane

graph is a cubic graph.

Answer : Maximum plane graph is triangulated . So

each region in the graph is bounded by 3 edges
.When we construct a dual graph of this MPG then
each region becomes a vertex in the dual graph and
its associated edges are 3 because each region is
bounded by 3 edges .
8. Show that every graph with at most three cycles is
planar.
9. Let G be a simple planar graph with no C3.Show
that G has a vertex of degree at most three.

Let all the vertices have at least 4 degree . So in total the edge e >= (4v /2 ) . v is total
number of vertices. But e <= 2v- 4 imply that 2v <= e <=2v-4 => 2v <= 2v -4 . This is a
contradiction . So there is at least a degree of at most 3.
10. Can you construct a plane graph whose dual
graph is disconnected? Justify your answer.

---> No.
Case(i) Can construct for connected planar graph
.(why??)
case(ii) : Can also construct for disconnected graph.
11. Give an example of a self-dual graph of seven
vertices.
12. Prove that a plane connected graph is bipartite if
and only if its dual is an Eulerian graph.
 Chapter - 7

2. Determine the chromatic number of Petersen graph.

Ans: 3 -colorable .

3. Show that dual graph of a maximal plane graph is a

cubic graph.
Maximum plane graph is triangulated . So
each region in the graph is bounded by 3 edges
.When we construct a dual graph of this MPG then
each region becomes a vertex in the dual graph and
its associated edges are 3 because each region is
bounded by 3 edges .

4. Let G be a simple planar graph containing no

triangle. Then show that X(G) < 4 . (X(G) -> chromatic
number)
(Let G be a simple planar graph containing no triangles. (i) Using Euler’s formula,
show that G contains a vertex of degree at most 3. (ii) Use induction to deduce that G
is 4-colorable.)
For the first part we can use Euler's F−E+V=2, where F
is the number of faces (counting the face that includes ∞),
E is the number of edges, and V the number of vertices.
If there are no triangles then each face is enclosed by at
least 4 edges.So 4F/2<E, i.e. F<E/2. From this we get
V>E/2+2. If all vertices have order ≥4 then 4V/2<E, i.e.
V<E/2. From this we get 0>2. So, we cannot have no
triangles and at the same time all vertices with degree ≥4

For the second part take a vertex that has degree ≤3

Color it and its neighbors with different colors A,B,C,D. We
can do this only because it has degree ≤3. We can delete
this vertex and the edges incident on it. If we color the rest
of the graph there is always a way to color the deleted
vertex. Notice that the graph with this vertex deleted still
has no triangles, but less vertices. Apply induction on the
number of vertices now.

ii>
a triangle-free planar graph always has a vertex with
degree 3 or less. any graph on 4 (or less) vertices is
4-colourable

Lets say , every triangle-free planar graph on n vertices is

4-colourable. Now take any triangle-free planar graph on
(n+1) vertices.
If the graph has a vertex with degree three or less then
remove it, the remaining graph can be 4 coloured by the
induction hypothesis. The removed vertex had 3 or less
neighbours only so we can colour it using the fourth
colour.

There is always a vertex having degree 3 or less. We can

suppose that the graph is connected and has at least 4
vertices.

If it is not connected than take any connected component

of the graph. Every face has at least 4 edges. Hence the
number of edges is at least 2f. v-e+f=2 implies v-e+e/2 is
at least 2. So, on one hand e<=2v-4.

On the other hand the sum of the degrees is 2e. If every

vertex had degree 4 or larger then 2e would be at least 4v
which is not possible since e<=2v-4.

Hence we could deduce that G is 4 colourable.

5. Show that for a tree of n vertices PG(k) = k(k −
1)^(n−1).

6. Construct a 4-critical graph.

Ans : K4
7. Let G be a k-critical graph. Then show that the degree
of every vertex of G is at least k-1.
 Chapter - 8

4. Prove that a connected acyclic digraph always has a

source and a sink.

5. Let T be any tournament. Prove that the converse of T

and the complement of T are isomorphic.

Here Converse(T) U T = Complete (T)

So Converse(T) = Complete(T) \ T
But by definition it’s Complement (T) .
So converse(T) = Complement(T)
Both are the same graph . So isomorphic.
 Chapter-9

1. Show that every maximal outerplanar graph contains at

least two vertices of degree 2.
(Fact 9.2.2 Every biconnected outerplanar graph has at
least two vertices of degree 2.)
Ans:
Observe that a leaf vertex of the weak dual tree T of an
outerplanar graph G corresponds to a face of G containing a
vertex of degree 2. If T is a tree of a single vertex, then G is a
triangle and G contains exactly three vertices of degree 2. If T
has two or more vertices then T has at least two leaves, and
hence the following fact holds.

2.Let n2 be the number of vertices of degree 2 and t be the

number of internal triangles in a maximal outerplanar graph
with n vertices. If n> 4 then prove t = n2 - 2.
4. Find canonical ordering of the graph in Fig. 9.24.

Ans:

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14

a b g h f k j i e o d l m c
5. Identify all separating triangles in Fig. 9.24 and construct a
genealogical tree of separating triangles.

Ans : ST are → aec , ced, med, aeg , ehg , efg , ekg

6. Construct a clique tree for the graph in Fig. 9.25.

7. Find a perfect elimination scheme for the graph in Fig. 9.25.
Ans :
(abcdefgh)
=> (ab) (cdefg) (h)
=> (b) (a) (de) (cf) (g) (h)
=> (b) (a) (d) (e) (c) (f) (g) (h)

8. Show that all vertex-induced subgraphs of a chordal graph

are also chordal graphs.
Ans : Both have cycles with chordals .

9. Construct a tree decomposition of the graph in Fig. 9.25

which is not a clique tree.
10. Construct a SPQ-tree decomposition of the graph in Fig.