## Graph Theory | Engineering Mathematics

Question 1 |

The number of edges in a regular graph of degree d and n vertices is

Maximum of n and d | |

N + d | |

Nd | |

Nd / 2 |

Question 1 Explanation:

**In graph theory**, A graph is called regular graph if degree of each vertex is equal.

A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

Let us say,

degree = d

vertices = n

**Total degrees of all the vertices is n*d**

Each edge will be increasing the total degree by 2,

So Total edges = nd/2

**Alternative :**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

E=nd/2

Question 2 |

Consider the graph shown in the figure below:

Which of the following is a valid strong component?

Which of the following is a valid strong component?

A, c, d | |

A, b, d | |

B, c, d | |

A, b, c |

Question 2 Explanation:

A directed graph is

The given graph has (a, b, c) as a strongly connected component.

**strongly connected**if there is a path between all pairs of verticesThe given graph has (a, b, c) as a strongly connected component.

Question 3 |

If G is a graph with e edges and n vertices, the sum of the degrees of all vertices in G is

E | |

E/2 | |

E ^{2} | |

2 e |

Question 3 Explanation:

**Theorem :**In any graph G with e edges, the sum of the degrees of all the vertices = 2* e

**Alternative**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

.

Question 4 |

If G is a graph with e edges and n vertices, the sum of the degrees of all vertices in G is

E | |

E/2 | |

E ^{2} | |

2e |

Question 4 Explanation:

**Theorem :**In any graph G with e edges, the sum of the degrees of all the vertices = 2* e.

**Alternative :**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

Question 5 |

If G is a graph with e edges and n vertices, the sum of the degrees of all vertices in G is

E | |

E/2 | |

E ^{2} | |

2 e |

Question 5 Explanation:

**Theorem :**In any graph G with e edges, the sum of the degrees of all the vertices = 2* e.

**Alternative :**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

Question 6 |

A given connected graph is a Euler Graph if and only if all vertices of are of

Same degree | |

Even degree | |

Odd degree | |

Different degree |

Question 6 Explanation:

**Euler Graph :**

A given connected graph G is a Euler Graph if and only if all vertices of G are of

**even degree**.

(OR)

An Euler Graph is a connected graph that contains an Euler Circuit.

So option(B) is correct answer

Above graph is a connected graph and all its vertices are of even degree. So, it is an Euler graph.

Alternatively, the above graph contains an Euler circuit

**BACEDCB**, Therefore, it is an Euler graph.

Question 7 |

The maximum number of edges in a n-node undirected graph without self loops is

n ^{2} | |

n(n-1)/2 | |

n-1 | |

n(n+1)/2 |

Question 7 Explanation:

**Maximum number of edges in a undirected graph with n nodes ?**

In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N

**(N−1)/2.**

**Maximum number of edges in a directed graph with n nodes ?**

If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is

**N * (N - 1)**.

**Alternative :**

The maximum number of edges in an n node undirected graph G (n, e) without self-loops is present in a complete graph (Kn):

A complete graph is a graph with N vertices and an edge between every two vertices.

- There are no loops.
- Every 2 vertices share exactly one edge.

_{N}for a complete graph with N vertices.

**Example :**

Question 8 |

A graph in which all nodes are of equal degree, is known as

Multigraph | |

Non regular graph | |

Regular graph | |

Complete graph |

Question 8 Explanation:

**In graph theory**, A graph is called regular graph if degree of each vertex is equal.

A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

**Number of edges in a regular graph of degree d and n vertices is**?

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

E=nd/2

**Complete graph**

A complete graph is a graph with N vertices and an edge between every two vertices.

- There are no loops.
- Every 2 vertices share exactly one edge.

_{N}for a complete graph with N vertices.

**Example :**

**Multigraph**

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.

Question 9 |

In a graph G there is one and only one path between every pair of vertices then G is a

Path | |

Walk | |

Tree | |

Circuit |

Question 9 Explanation:

**Theorem**: If in a graph G there is one and only one path between every pair of vertices than graph G is a tree.

**Proof**: There is the existence of a path between every pair of vertices so we assume that graph G is connected. A circuit in a graph implies that there is at least one pair of vertices a and b, such that there are two distinct paths between a and b. Since G has one and only one path between every pair of vertices. G cannot have any circuit. Hence graph G is a tree.

Question 10 |

A simple graph ( a graph without parallel edge or loops) with n vertices and k components can have at most

N edges | |

N-k edges | |

(n − k)(n − k + 1) edges | |

(n − k)(n − k + 1)/2 edges |

Question 10 Explanation:

Question 11 |

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between

K and n | |

K-1 and k+1 | |

K-1 and n-1 | |

K+1 and n-k |

Question 11 Explanation:

If a vertex is removed from the graph G, with n nodes and k components

Number of components decreased by one = k−1 (The removed vertex itself is a isolated vertex which was a component)

Number of components =n−1 ( consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other n−1 vertices isolated making n−1 components)

**Minimum :**Number of components decreased by one = k−1 (The removed vertex itself is a isolated vertex which was a component)

**Maximum:**Number of components =n−1 ( consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other n−1 vertices isolated making n−1 components)

Question 12 |

How many edges are there in a forest with

*v*vertices and*k*components?(v+1)−k | |

(v+1)/2 −k | |

v−k | |

v+k |

Question 12 Explanation:

A forest is a graph with no cycles; a tree is a connected graph with no nontrivial closed trails.

Thus, a forest is a disjoint union of trees.

Thus, a forest is a disjoint union of trees.

**Each connected component is a tree**Question 13 |

The number of edges in a ‘n’ vertex complete graph is ?

N * (n-1) / 2 | |

N * (n+1) / 2 | |

N ^{2} | |

N * (n+1) |

Question 14 |

To guarantee correction of upto t errors, the minimum Hamming distance dmin in a block code must be

T+1 | |

T−2 | |

2t−1 | |

2t+1 |

Question 14 Explanation:

To guarantee correction of upto t errors, the minimum Hamming distance dmin in a block code must be

**dmin = 2t + 1**- The Hamming distance between two words is the number of differences between corresponding bits.
- To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be
**dmin = s+1.** - To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be
**dmin = 2t + 1.** - k – number of data bits, r – number of redundant bits, n – Number of code bits
- n = k + r
- 2
^{r}≥ k + r + 1 where, r = redundant bit, k = data bit - Example : k = 4; then r = 3

Question 15 |

**Which of the following statements is/are TRUE for an undirected graph?**

**P**: Number of odd degree vertices is even

**Q**: Sum of degrees of all vertices is even

P only | |

Q only | |

Both P and Q | |

Neither P nor Q |

Question 15 Explanation:

**P :**Number of odd degree vertices is even -

**True**

**Q**: Sum of degrees of all vertices is even -

**True**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

- The sum of degree of all the vertices is always even.
- The sum of degree of all the vertices with odd degree is always even.
- The number of vertices with odd degree are always even.

Question 16 |

No bridges | |

{d,e} | |

{c,d} | |

{c,d} and {c,f} |

Question 16 Explanation:

- An edge in an undirected connected graph is a
**bridge**if removing it disconnects the graph. - For a disconnected undirected graph : A
**bridge**is an edge removing which increases number of disconnected components - If we remove { d-e } edge then there is no way to reach out to vertex e and the graph is disconnected.
- So, In the above given graph only edge {d-e} is a bridge since its removal produces 2 components.

Question 17 |

The following graph nas no Euler circuit because

It has 7 vertices | |

It is even-valent(all vertices have even valence) | |

It is not connected | |

It does not have a Euler circuit |

Question 17 Explanation:

The above graph has no Euler circuit because Graph is not connected.

**Concept :**Question 18 |

For the graph shown, which of the following paths is a Hamilton circuit?

ABCDCFDEFAEA | |

AEDCBAF | |

AEFDCBA | |

AFCDEBA |

Question 18 Explanation:

A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

**Option(A)**: It is not Hamiltonian circuit because A,F and E are repeated several times.**Option(B)**: It is not Hamiltonian circuit because start and end vertex are different it means, not closed walk.**Option(C)**: It is Hamiltonian circuit because it is closed walk it means, start and end vertex are same and all vertex are traversed once with no repeats.**Option(D)**: It is not Hamiltonian circuit because it is not closed walk.Question 19 |

Choose the most appropriate definition of plane graph.

A simple graph which is isomorphic to hamiltonian graph | |

A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y | |

A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices | |

None of the option |

Question 19 Explanation:

- In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
- In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.
- A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Question 20 |

The K-coloring of an undirected graph **G = (V, E)** is a function

**C : V ➝ {0, 1, ......, K-1}** such that** c(u)≠c(v)** for every edge **(u,v) ∈ E**

Which of the following is not correct?

G has no cycles of odd length | |

G has cycle of odd length | |

G is 2-colorable | |

G is bipartite |

Question 20 Explanation:

Graph that can be 2-colored are bipartite graph. To check if a given graph is bipartite, we run BFS starting from any node then we check

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning

V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning

V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

- A cycle of length n>=3 is – chromatic if n is even and 3- chromatic if n is odd
- A graph is bi- colourable (2- chromatic) if and only if it has no odd cycles.
- A non - empty graph G is bi colourable if and only if G is bipartite.

Question 21 |

If a graph (G) has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if

**(i)**deg(v) ≥ n/3 for each vertex v

**(ii)**deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.

**(iii)**E(G) ≥ 1/3(n-1)(n-2) + 2

Choose the correct answer for the code given below:

**Code:**

(i) and (iii) only | |

(ii) and (iii) only | |

(iii) only | |

(ii) only |

Question 21 Explanation:

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

The maximum number of edges for a graph to be non-hamiltonian is

Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

E(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

So, option (D) is correct.

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

**So Statement(i) is false**According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

**So Statement(ii) is True**The maximum number of edges for a graph to be non-hamiltonian is

^{(n−1)}C_{2}+1.Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

^{4−1}C_{2 }+ 1=3+1=4. therefore, if the number of edges is ≤4, then the graph can be non-hamiltonianE(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

**|E(G)| ≥ 1/2(n – 1) (n – 2) + 2**Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

**Statement(iii) is false.**So, option (D) is correct.

Question 22 |

The number of independent loops for a network with n nodes and b branch is

N-1 | |

B-n | |

B-n+1 | |

Independent of "the number of nodes |

Question 22 Explanation:

For any circuit or network,

Where,

**M = B - n + 1**Where,

**M**= Number of mesh (independent loop)**B**= Number of branches**n**= Number of nodes**Concept :**- For a circuit with n nodes, there are n − 1 independent node equations that constrain the currents. If the circuit has b branches, that implies that there are exactly
**b−(n−1) = b−n+ 1**independent loops currents. - For planar circuits (circuits that can be drawn on a plane without any elements crossing one another), there is an obvious choice for the loops; namely, the
**b − n + 1**small loops that enclose no circuit elements. - For nonplanar loops, the choice is not so obvious, but the number of independent loops will be
**b − n + 1**

Question 23 |

The number of circuits in a tree with 'n' nodes is

Zero | |

One | |

N-1 | |

N/2 |

Question 23 Explanation:

- A tree is a connected subgraph of a network which consists of all the nodes of the original graph but no closed paths.
- The graph of a network may have a number of trees.
- The number of nodes in a graph is equal to the number nodes in the tree. The number of branches in a tree is less than the number of branches in a graph.
- A graph is a tree if there is a unique path between any pair of nodes.'
- In general, if a tree contains n nodes, then it has (n-1) branches. In forming a tree for a given graph, certain branches are removed or opened.
- The branches thus opened are called links or link branches Thus the link branches and the tree branches combine to form the graph of the entire network.
- A circuit in such a tree is impossible.

Question 24 |

A complete graph with "n" vertices is

2-chromatic | |

(n/2) chromatic | |

(n-1) chromatic | |

N-Chromatic |

Question 24 Explanation:

- The minimum number k for which there is a k-colouring of the graph is called the chromatic number (chromatic index) of G and is denoted by χ(G). If χ(G) = k, the graph G is said to be k-chromatic.
- A
**complete graph with n vertices is n-chromatic**, because all its vertices are adjacent. So, χ(K_{n}) = n and χ( K_{n}') = 1. Therefore we see that a graph containing a complete graph of r vertices is at least r-chromatic. For example, every graph containing a triangle is at least 3-chromatic.

Question 25 |

Minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is

2 | |

3 | |

4 | |

n-2⌈(n/2)⌉+2 |

Question 25 Explanation:

Chromatic Number for cycle graph

Option (D) :

Substitute n = 3 and n = 4 in given equation

**1)**Chromatic number is 2 If number of vertices in cycle graph is even**2)**Chromatic number is 3 If number of vertices in cycle graph is oddOption (D) :

**n-2⌈(n/2)⌉+2**is a representation for this. So Option(D) is correct AnswerSubstitute n = 3 and n = 4 in given equation

**n-2⌈(n/2)⌉+2**. Then we will get the desired answer.**Example :**Question 26 |

Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to:

3 | |

4 | |

5 | |

6 |

Question 26 Explanation:

**For any planar graph,**

v - e + f = 2

Where,

v = Number of vertices

e = Number of edges

f = Number of faces including bounded and unbounded

f =15−10+2=7

Number of bounded faces =number of faces -1

=7−1=6

Therefore, option(D) is correct answer

Question 27 |

Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is

E | |

2E | |

V | |

2V |

Question 28 |

A path in graph G, which contains every vertex of G and only Once?

Euler circuit | |

Hamiltonian path | |

Euler Path | |

Hamiltonian Circuit |

Question 28 Explanation:

- A
**circuit**is a walk that starts and ends at a same vertex, and contains no repeated edges. - An
**Eulerian circuit**in a graph G is a circuit that includes all vertices and edges of G. A graph which has an Eulerian circuit is an Eulerian graph. - A
**Hamiltonian circuit**in a graph G is a circuit that includes every vertex (except first/last vertex) of G exactly once. - An
**Eulerian path**in a graph G is a walk from one vertex to another, that passes through all vertices of G and traverses exactly once every edge of G. An Eulerian path is therefore not a circuit. - A
**Hamiltonian path**in a graph G is a walk that includes every vertex of G exactly once. A Hamiltonian path is therefore not a circuit.

Question 29 |

Considering the following graph, which one of the following set of edged represents all the bridges of the given graph?

(a,b)(e,f) | |

(a,b),(a,c) | |

(c,d)(d,h) | |

(a,b) |

Question 29 Explanation:

- An edge in an undirected connected graph is a
**bridge**if removing it disconnects the graph. - For a disconnected undirected graph : A
**bridge**is an edge removing which increases number of disconnected components - If we remove { a-b } edge then there is no way to reach out to vertex b and then the graph is disconnected.
- If we remove { e-f } edge then there is no way to reach out to vertex f and then graph is disconnected.
- So, In the above given graph only edge { a-b } and { e-f } are bridges since its removal produces 3 components.

Question 30 |

Which of the following statements is/are TRUE?

**S1:**The existence of an Euler circuit implies that an euler path exists.**S2:**The existence of an Euler path implies that an Euler circuit exists.S1 is true | |

S2 is true | |

S1 and S2 both are true | |

S1 and S2 both are false |

Question 30 Explanation:

Eulerian Path is a path in graph that visits every edge exactly once. An Eulerian path is therefore not a circuit. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.

**True :**The existence of an Euler circuit implies that an Euler path exists.**False :**The existence of an Euler path implies that an Euler circuit exists.Question 31 |

A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by 13 edges, then the number of regions is:

5 | |

6 | |

7 | |

8 |

Question 31 Explanation:

**For any planar graph,**

v - e + R = 2Where,

v = Number of vertices

e = Number of edges

Number of regions/faces(R/f)=?

For any connected planner graph

V-E+R=2;

V+R=E+2;

R=E-V+2;

R=13−8+2=7

R=15−8=7

∴ Number of regions in given graph G is 7

Therefore, option(C) is correct answer

Question 32 |

Let G be a simple connected planar graph with 13 vertices and 19 edges. then the number of faces in the planar embedding of the graph is

6 | |

8 | |

9 | |

13 |

Question 32 Explanation:

**For any planar graph,**

v - e + f = 2Where,

v = Number of vertices

e = Number of edges

f = Number of faces

Given,

vertex v =13

Edges e =19

v - e + f = 2

v + f = e+2

f = e-v+2

f=19-13+2

f=21-13

f=8

Therefore, option(B) is correct answer

Question 33 |

The number of diagonals that can be drawn by joining the vertices of an octagon is

28 | |

48 | |

20 | |

None of the option |

Question 34 |

If a connected graph G has planar embedding with 4 faces and 4 vertices, then what will be the number of edges in G?

7 | |

6 | |

4 | |

3 |

Question 34 Explanation:

**For any planar graph,**

v - e + f = 2Where,

v = Number of vertices

e = Number of edges

f = Number of faces

Given,

vertex v =4

Faces f=4

Edges e =?

v - e + f = 2

4-e+4=2

-e+8=2

8=2+e

e=8-2

e=6

Therefore, option(B) is correct answer

Question 35 |

Every cut set of a connected euler graph has____

An odd number of edges | |

At least three edges | |

An even number of edges | |

A single edge |

Question 35 Explanation:

If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.

Question 36 |

A graph G is dual if and only if G is a ___

Euler graph | |

Regular graph | |

Complete graph | |

Planar graph |

Question 36 Explanation:

Question 37 |

What is the chromatic number of an n-vertex simple connected graph, which does NOT contain any odd-length cycle?

N | |

N-1 | |

2 | |

3 |

Question 37 Explanation:

**Theorem.**A graph G is bipartite if and only if it has no odd cycles.

**Proof**. First, suppose that G is bipartite. Then since every subgraph of G is also bipartite, and since odd cycles are not bipartite, G cannot contain an odd cycle. That’s the easy direction. Now suppose that G is a non-trivial graph that has no odd cycles. We must show that G is bipartite. So we must determine a partition of the vertices of G into independent sets. It is enough to prove our result for connected graphs since if G is bipartite, so is every component of G (and vice versa).

**Refer page number 2:**https://people.math.sc.edu/sumner/math575spring2009/handouts/Bipartite%20graphs.pdf

**Bipartite Graph:**A graph which is 2-colorable is called bipartite.

**Refer page number 5**: https://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_9.pdf

**Bipartite graphs**: By definition, every bipartite graph with at least one edge has chromatic number 2.(otherwise 1 if graph is null graph )

**Refer page number 1**: https://web.math.ucsb.edu/~padraic/mathcamp_2011/introGT/MC2011_intro_to_GT_wk1_day4.pdf

Chromatic Number=2 So, option(C) is the correct answer.

Question 38 |

Considering an undirected graph, which of the following statements is/are true?

**(i)**Number of vertices of odd degree is always even**(ii)**Sum of degrees of all the vertices is always evenNeither (i) nor (ii) | |

Both (i) and (ii) | |

Only (ii) | |

Only (i) |

Question 38 Explanation:

**P :**Number of odd degree vertices is even -

**True**

**Q**: Sum of degrees of all vertices is even -

**True**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

- The sum of degree of all the vertices is always even.
- The sum of degree of all the vertices with odd degree is always even.
- The number of vertices with odd degree are always even.

Question 39 |

Select the option that best describes the relationship between the following graphs:

G and H are directed | |

G and H are isomorphic | |

G and H are homomorphic | |

G and H are not isomorphic |

Question 39 Explanation:

Given graphs are isomorphic if it satisfies the below rules

Graph G and H are having same number of vertices and edges. Total Both the graphs have 6 vertices, 9 edges So, it satisfied first and second rule.

The degree sequence is also same.

→ M1 degree 2, M2 degree 3, M3 degree 3, M4 degree 2, M5 degree 3, M6 degree 3.

→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.

But second graph has a circuit of length 3 and the minimum length of any circuit in the first graph is 4. Therefore the given graphs are not isomorphic.

- Equal number of vertices.
- Equal number of edges.
- Same degree sequence
- Same number of circuit of particular length

Graph G and H are having same number of vertices and edges. Total Both the graphs have 6 vertices, 9 edges So, it satisfied first and second rule.

The degree sequence is also same.

→ M1 degree 2, M2 degree 3, M3 degree 3, M4 degree 2, M5 degree 3, M6 degree 3.

→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.

But second graph has a circuit of length 3 and the minimum length of any circuit in the first graph is 4. Therefore the given graphs are not isomorphic.

Question 40 |

The number of the edges in a regular graph of degree 'd' and 'n' vertices is____

Maximum of n,d | |

n+d | |

nd | |

nd/2 |

Question 40 Explanation:

**In graph theory**, A graph is called regular graph if degree of each vertex is equal.

A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

Let us say,

degree = d

vertices = n

**Total degrees of all the vertices is n*d**

Each edge will be increasing the total degree by 2,

So Total edges = nd/2

**Alternative :**

**By handshaking Lemma:**

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**

n × d = 2 × e

E=nd/2

Question 41 |

A minimal subgraph G’ of G such that V(G’)=V(G) and G’ is connected is called:

A spanning tree | |

A connected graph | |

A directed graph | |

A biconnected component |

Question 41 Explanation:

- A minimal subgraph G’ of G such that V(G’)=V(G) and G’ is connected is called a spanning tree
- Spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible no. of edges. Therefore, a spanning tree does not contain any cycles and it cannot be disconnected.

Question 42 |

Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)| = n ≥ 3. Then which of the following is true ?

Deg(v) ≥n/2 for each vertex v. | |

|E(G)| ≥1/2(n – 1) (n – 2) + 2 | |

Deg (v) + deg(w) ≥ n whenever v and w are not connected by an edge | |

All of the above |

Question 42 Explanation:

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

The maximum number of edges for a graph to be non-hamiltonian is

Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

So, option (D) is correct.

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

**So Statement(i) is True**According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

**So Statement(iii) is True**The maximum number of edges for a graph to be non-hamiltonian is

^{(n−1)}C_{2}+1. Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph**Statement(ii) : |E(G)| ≥ 1/2(n – 1) (n – 2) + 2**Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

**Statement(ii) is True.**So, option (D) is correct.

Question 43 |

Given the following graphs:
Which of the following is correct?

G _{1} contains Euler circuit and G _{2} does not contain Euler circuit. | |

G _{1} does not contain Euler circuit and G _{2} contains Euler circuit. | |

Both G _{1} and G_{ 2} do not contain Euler circuit. | |

Both G _{ 1} and G_{ 2} contain Euler circuit. |

Question 43 Explanation:

**Both G**

-G

_{1} and G_{2} do not contain Euler circuit.-

_{1}have odd number of vertices. So, it is not Euler Circuit

**-**G

_{2}have odd number of vertices. So, it is not Euler Circuit

So, option(C) is the correct answer

**Concept :**

**Criterion for Euler Path**

If a graph G has an Euler path, then it must have exactly two odd vertices.

**(Or)**

If the number of odd vertices in G is anything other than 2, then G cannot have an Euler path.

**Criterion for Euler Circuits**

If a graph G has an Euler circuit, then all of its vertices must be even vertices.

**(Or)**

If the number of odd vertices in G is anything other than 0, then G cannot have an Euler circuit.

Question 44 |

The number of different spanning trees in complete graph, K

_{4} and bipartite graph, K_{2,2} have ______ and _______ respectively.14, 14 | |

16, 14 | |

16, 4 | |

14, 4 |

Question 44 Explanation:

**For any complete graph K**

_{n}with n nodes, different spanning trees possible is n^{(n-2)}Therefore, Number of spanning trees in complete graph K

**will be 4**

_{4}^{(4 - 2)}=4

^{2}= 16.

**For any Bipartite graph K**

_{m,n}with m and n nodes, different spanning trees possible is m^{(n-1)}.n^{(m-1)}Therefore, Number of Spanning trees in K

_{2,2}will be 2

^{(2-1)}* 2

^{(2-1)}. = 2 * 2 = 4.

Question 45 |

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below?

2 | |

4 | |

5 | |

6 |

Question 45 Explanation:

Definition already mentioned in the question.

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph

Therefore, Total 5 cliques are possible in the given graph

**Clique :**A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph

Therefore, Total 5 cliques are possible in the given graph

Question 46 |

Which of the following statement(s) is/are false ?

**(a)**A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.**(b)**A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.**(c)**A complete graph (K_{ n} ) has a Hamilton Circuit whenever n ≥ 3.**(d)**A cycle over six vertices (C_{6} ) is not a bipartite graph but a complete graph over 3 vertices is bipartite.(a) only | |

(b) and (c) | |

(c) only | |

(d) only |

Question 46 Explanation:

**Statement(A) : True**

**Theorem 1.**Euler’s Theorem. For a connected multi-graph G, G is Eulerian if and only if every vertex has even degree.

**Proof:**If G is Eulerian then there is an Euler circuit, P, in G. Every time a vertex is listed, that accounts for two edges adjacent to that vertex, the one before it in the list and the one after it in the list. This circuit uses every edge exactly once. So every edge is accounted for and there are no repeats. Thus every degree must be even.

Suppose every degree is even. We will show that there is an Euler circuit by induction on the number of edges in the graph. The base case is for a graph G with two vertices with two edges between them. This graph is obviously Eulerian

**Refer :**https://courses.engr.illinois.edu/cs173/su2014/Lectures/Euler.pdf

**Statement(B) : True**

Theorem 2: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

Theorem 2

**Proof:**

(ONLY IF) Assume the graph has an Euler path but not a circuit. Notice that every time the path passes through a vertex, it contributes 2 to the degree of the vertex (1 when it enters, 1 when it leaves). Obviously the first and the last vertices will have odd degree and all the other vertices - even degree. (IF) Assume exactly two vertices, u and v, have odd degree. If we connect these two vertices, then every vertex will have even degree. By Theorem 1, there is an Euler circuit in such a graph. If we remove the added edge {u,v} from this circuit, we will get an Euler path for the original graph.

**Statement(C) : True**

Theorem 3: A complete graph (Kn ) has a Hamilton Circuit whenever n ≥ 3.

Theorem 3

**Proof :**Let v1, . . . , vn be any way of listing the vertices in order. Then v1 − v2 − · · · − vn − v1 is a Hamilton circuit since all edges are present.

In general, having lots of edges makes it easier to have a Hamilton circuit.

**Statement(D) : False**

Question 47 |

Consider the graph given below: The two distinct sets of vertices, which make the graph bipartite are:

(v _{1} , v_{ 4} , v_{ 6} ); (v_{ 2} , v_{ }3 , v_{ 5} , v_{ 7} , v_{ 8} ) | |

(v _{1} , v_{ 7} , v_{ 8} ); (v_{ 2} , v_{ 3} , v_{ 5} , v_{ 6} ) | |

(v _{1} , v_{ 4} , v_{ 6} , v_{ 7} ); (v_{ 2} , v_{ 3} , v_{ 5} , v_{ 8} ) | |

(v _{1} , v_{ 4} , v_{ 6} , v_{ 7} , v_{ 8} ); (v_{ 2} , v_{ 3} , v_{ 5} ) |

Question 47 Explanation:

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

It is not bipartite graph because V

It is not bipartite graph because V

It is bipartite graph because it follows properties of bipartite and no two colours are adjacent.

(v1,v4,v6,v7 ) these vertex are with red color

(v2,v3,v5,v8) these vertex are with black color

It is not bipartite graph because because V

**Bipartite graphs are equivalent to two-colorable graphs**that is coloring of the vertices using two colors in such a way that vertices of the same color are never adjacent along an edge.**Option(A) - FALSE**It is not bipartite graph because V

_{5}, V_{7}and V_{3}are adjacent.**Option(B) - FALSE**It is not bipartite graph because V

_{5}, V_{6}and V_{2}are adjacent.**Option(C) - TRUE**It is bipartite graph because it follows properties of bipartite and no two colours are adjacent.

(v1,v4,v6,v7 ) these vertex are with red color

(v2,v3,v5,v8) these vertex are with black color

**Option(D) - FALSE**It is not bipartite graph because because V

_{4}, V_{6}and V_{8}are adjacent.Question 48 |

A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2,....n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?

(a) and (b) | |

(b) and (c) | |

(a) and (c) | |

(a), (b) and (c) |

Question 48 Explanation:

Question 49 |

Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ?

**(a)**deg (v) ≥ n / 2 for each vertex of G**(b)**|E(G)| ≥ 1 / 2 (n - 1) (n - 2) + 2 edges**(c)**deg (v) + deg (w) ≥ n for every n and v not connected by an edge.(a) and (b) | |

(b) and (c) | |

(a) and (c) | |

(a), (b) and (c) |

Question 49 Explanation:

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

So, option (D) is correct.

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

**So Statement(i) is True**According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

**So Statement(iii) is True****Statement(ii) : |E(G)| ≥ 1/2(n – 1) (n – 2) + 2**Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.

Refer : https://www.quora.com

Therefore,

**Statement(ii) is True**So, option (D) is correct.

Question 50 |

A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph ?

5 | |

N-3 | |

20 | |

11 |

Question 50 Explanation:

Given,

Two vertices of degree 4,

One vertex of degree 3,

One vertex of degree 2,

Vertex of degree 1 is unknown,

Now assume k be the number of vertex of degree 1.

Total Number of vertex = 2 + 1 + 1 + k = 2+2+k=k + 4.

We now that Total Number of vertex =k+4

= k + 4 – 1

= k + 3

2 * 4 + 1 * 3 + 1 * 2 + 1 * K = 2 * (Number of edges)

=13 + k = 2 * (k + 3)

k = 7.

Total number of vertex = 7 + 4 = 11.

Hence, option(D) is correct answer.

In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

n × d = 2 × e

Two vertices of degree 4,

One vertex of degree 3,

One vertex of degree 2,

Vertex of degree 1 is unknown,

Now assume k be the number of vertex of degree 1.

Total Number of vertex = 2 + 1 + 1 + k = 2+2+k=k + 4.

**Total Number of edges = Total Number of vertex – 1**We now that Total Number of vertex =k+4

= k + 4 – 1

= k + 3

**Now Apply handshaking lemma**2 * 4 + 1 * 3 + 1 * 2 + 1 * K = 2 * (Number of edges)

=13 + k = 2 * (k + 3)

k = 7.

Total number of vertex = 7 + 4 = 11.

Hence, option(D) is correct answer.

**Concept :****Handshaking Lemma:**In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that

**sum of degrees = 2 * number of edges**n × d = 2 × e

Question 51 |

Complete Graph | |

Bipartite Graph | |

Hamiltonian Graph | |

All of the above |

Question 51 Explanation:

**Option(A) :**It is not complete graph because there is no edge between vertex A and C, D and B and another thing is number edges is not equal to n*(n-1)/2 edges. If it is complete graph then it must have

**n * (n – 1) / 2**edges.

**Option(B) :**This graph is not bipartite. If a graph is 2-colorable then it is bipartite but this graph have more then 2 colors.

**Option(C) :**According to Dirac's theorem when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.

So, option(C) is correct

Question 52 |

Consider the following statements related to AND-OR Search algorithm.

Which one of the following is true referencing the above statements?

Choose the correct answer from the code given below:

**S1** : A solution is a subtree that has a goal node at every leaf.**S2** : OR nodes are analogous to the branching in a deterministic environment**S3** : AND nodes are analogous to the branching in a non-deterministic environment.Which one of the following is true referencing the above statements?

Choose the correct answer from the code given below:

S1- False, S2- True, S3- True | |

S1- True, S2- True, S3- True | |

S1- False, S2- True, S3- False | |

S1- True, S2- True, S3- False |

Question 52 Explanation:

AND OR search algorithm finds goal node at each state in order to reach the final goal state. It works in non-deterministic environment.

**A solution for an AND-OR search problem is a subtree that****(1)**has a goal node at every leaf**(2)**specifies one action at each of its OR nodes**(3)**includes every outcome branch at each of its AND nodes**And OR search algorithm works in the following way:****(1)**It has to find a solution tree of subtrees.**(2)**Solution tree contains the root of the subtrees.**(3)**If a non-terminal AND node is in subtree and solution tree then all its children are in solution tree.**(4)**If a non-terminal OR node is in subtree and solution tree then exactly one of its children are in solution tree.**AND OR search**tree may contain nodes that root identical subtrees (sub problems with identical optimal solutions) which can be unified. When unifiable nodes are merged, search tree becomes a graph and its size becomes smaller.**Determinism**: each action has a unique outcome: if chose to drive from**Non-deterministic**:Each action has a set of possible outcomes (resulting states) A solution is not a sequence of actions, but a contingency plan, or a strategy: if after pushing the lift button, lift arrives, then take the lift; else take the stairs.Question 53 |

The K-coloring of an undirected graph

Which of the following is not correct?

**G=(V,E)**is a function**C: V➝{0,1,......,K-1}**such that**c(u)≠c(v)**for every edge**(u,v) ∈ E**Which of the following is not correct?

G has no cycles of odd length | |

G has cycle of odd length | |

G is 2-colorable | |

G is bipartite |

Question 53 Explanation:

Graph that can be 2-colored are bipartite graph. To check if a given graph is bipartite, we run BFS starting from any node then we check

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning

V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning

V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

- A cycle of length n>=3 is – chromatic if n is even and 3- chromatic if n is odd
- A graph is bi- colourable (2- chromatic) if and only if it has no odd cycles.
- A non - empty graph G is bi colourable if and only if G is bipartite.

Question 54 |

If a graph (G) has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if

**(i)**deg(v) ≥n/3 for each vertex v**(ii)**deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.**(iii)**E (G) ≥ 1/3 (n − 1 )(n − 2 ) + 2(i) and (iii) only | |

(ii) and (iii) only | |

(iii) only | |

(ii) only |

Question 54 Explanation:

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

The maximum number of edges for a graph to be non-hamiltonian is

Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

E(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

Therefore,

So, option (D) is correct.

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.

**So Statement(i) is false**According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.

**So Statement(ii) is True**The maximum number of edges for a graph to be non-hamiltonian is

^{(n−1)}C_{2}+1.Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

^{4−1}C_{2 }+ 1=3+1=4. therefore, if the number of edges is ≤4, then the graph can be non-hamiltonianE(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

Therefore,

**Statement(iii) is false.**So, option (D) is correct.

Question 55 |

Consider the graph given below as : Which one of the following graph is isomorphic to the above graph ?

A | |

B | |

C | |

D |

Question 55 Explanation:

Given graphs are isomorphic if it satisfies the below rules

- Equal number of vertices.
- Equal number of edges.
- Same degree sequence
- Same number of circuit of particular length

**Option(A) :**It is not isomorphic graph because vertex v5 having degree 4**Option(B) :**It is not isomorphic because vertex v6 having degree 4.**Option(C) :**It is isomorphic because Every vertex has degree 3 and total no. of edges and vertices are 12 and 8.**Option(D) :**It is not isomorphic because Vertex v6 having degree 4.Question 56 |

Consider a complete bipartite graph km,n. For which values of m and n does this, complete graph have a Hamilton circuit

M = 3, n = 2 | |

M = 2, n = 3 | |

M = n ≥ 2 | |

M = n ≥ 3 |

Question 56 Explanation:

Question 57 |

Match List 1 with List 2 and choose the correct answer from the code given below :

where V and E are the number of vertices and edged in graph respectively.

where V and E are the number of vertices and edged in graph respectively.

**Code:**(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii) | |

(a)-(i), (b)-(iii), (c)-(ii), (d)-(iv) | |

(a)-(iii), (b)-(i), (c)-(ii), (d)-(iv) | |

(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii) |

Question 57 Explanation:

**Dijkstra’s algorithm**:

**Time Complexity**: O(V

^{2})

**Case-1:**

This case is valid when-

**The given graph G is represented as an adjacency matrix.****Priority queue Q is represented as an unordered list.**- A[i,j] stores the information about edge (i,j).
- Time taken for selecting i with the smallest dist is O(V).
- For each neighbor of i, time taken for updating dist[j] is O(1) and there will be maximum V neighbors.
- Time taken for each iteration of the loop is O(V) and one vertex is deleted from Q.
- Thus, total
**time complexity becomes O(V**^{2}).

**Case-2:**

This case is valid when-

**The given graph G is represented as an adjacency list.****Priority queue Q is represented as a binary heap.**- With adjacency list representation, all vertices of the graph can be traversed using BFS in O(V+E) time.
- In min heap, operations like extract-min and decrease-key value takes O(logV) time.
- So, overall time complexity becomes O(E+V) x O(logV) which is O((E + V) x logV) = O(ElogV)
- This
**time complexity can be reduced to O(E+VlogV) using Fibonacci heap.**

**Kruskal’s algorithm**:

**Time Complexity:**O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V^2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

**Floyd-Warshall algorithm**:The Floyd-Warshall all-pairs shortest path runs in O(n

^{3}) time .This is because we have a triple (3) for loop, each with n iterations to make

**Topological sorting**

**:**The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).

Question 58 |

Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is

2451 | |

4950 | |

4851 | |

9900 |

Question 58 Explanation:

Maximum number of edges in a simple graph

Where, k is the number of connected components(i.e. if graph is connected then k=1)

Given graph is disconnected so we have to take k=2 for maximum number of edges

=[(n-k)(n-k+1)] / 2

=[(n-2)(n-2+1)] / 2

=[(n-1)(n-2)] / 2

We assume k

So, Maximum number of edges in disconnected graph

=[(n-1)(n-2)] / 2

=[(100-1)(100-2)] / 2

=[(99)*(98)] / 2

=4851

Disconnected graph with 2 nodes have 0 edge =[(n-1)(n-2)] / 2= (2-1)(2-2)/2=0

Disconnected graph with 3 nodes have at most 1 edge =[(n-1)(n-2)] / 2=(3-1)(3-2)/2=1

Disconnected graph with 4 nodes have at most 3 edges between 3 nodes and 4

Disconnected graph with 5 nodes have at most 6 edges =[(n-1)(n-2)] / 2=(5-1)(5-2)/2=6

In general with n nodes have at most (n-1)(n-2)/2 edges

**[(n-k)(n-k+1)] / 2**Where, k is the number of connected components(i.e. if graph is connected then k=1)

Given graph is disconnected so we have to take k=2 for maximum number of edges

=[(n-k)(n-k+1)] / 2

=[(n-2)(n-2+1)] / 2

=[(n-1)(n-2)] / 2

We assume k

_{(n-1)}complete graph and other one vertexSo, Maximum number of edges in disconnected graph

=[(n-1)(n-2)] / 2

=[(100-1)(100-2)] / 2

=[(99)*(98)] / 2

=4851

**Examples :**Disconnected graph with 2 nodes have 0 edge =[(n-1)(n-2)] / 2= (2-1)(2-2)/2=0

Disconnected graph with 3 nodes have at most 1 edge =[(n-1)(n-2)] / 2=(3-1)(3-2)/2=1

Disconnected graph with 4 nodes have at most 3 edges between 3 nodes and 4

^{th}node as isolated vertex =[(n-1)(n-2)] / 2=(4-1)(4-2)/2=3Disconnected graph with 5 nodes have at most 6 edges =[(n-1)(n-2)] / 2=(5-1)(5-2)/2=6

In general with n nodes have at most (n-1)(n-2)/2 edges

Question 59 |

Consider the following statements :

Which of the above statements is/are true ?

**(i**) A graph in which there is a unique path between every pair of vertices is a tree.**(ii)**A connected graph with**e = v – 1**is a tree.**(iii)**A graph with**e = v – 1**that has no circuit is a tree.Which of the above statements is/are true ?

(i) & (iii) | |

(ii) & (iii) | |

(i) & (ii) | |

All of the above |

Question 59 Explanation:

**Statement(i) : A graph in which there is a unique path between every pair of vertices is a tree.**

Above statement is true because graph can have unique path only when it does not have cycle. If there is no cycles in graph then it a tree. A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.

**Statement(ii) : A connected graph with e = v − 1 is a tree.**

Above statement is true because

**Theorem 1**: Suppose |V | = n and |E| = n − 1. The following three statements become equivalent.

(a) G is connected.

(b) G is acyclic.

(c) G is a tree.

**Statement(ii) : A connected graph with e=v-1 that has no circuit is a tree.**

Above statement is true because they mentioned e=v-1 means graph is connected it is already discussed statement(ii).A connected graph without any circuit is called a Tree

Question 60 |

A simple graph G with n-vertices is connected if the graph has

(n – 1) (n – 2)/2 edges | |

More than (n – 1) (n – 2)/2 edges | |

Less than (n – 1) (n – 2)/2 edges | |

Σ ^{k}_{i}=1 C(n_{i}, 2) edges |

Question 60 Explanation:

- A simple graph with n vertices is connected if it has more than (n−1)(n−2) / 2 edges.
- Consider the highest number of edges a graph can have without being connected. It must have two connected components, and, to maximize the number of edges, they must be size n − 1 and 1. To maximize the edges, the large component must be a complete graph, which will have
**(n − 1)(n − 2)/2 edges.** - Maximum number of edges in a simple graph =
**[(n-k)(n-k+1)] / 2** - Where, k is the number of connected components(i.e. if graph is connected then k=1)
- If the graph is disconnected then we have to take k=2 for maximum number of edges =[(n-1)(n-2)] / 2
- We assume k
_{(n-1)}complete graph and other one vertex - So, Maximum number of edges in disconnected graph =[(n-1)(n-2)] / 2

Question 61 |

A graph is non-planar if and only if it contains a subgraph homomorphic to

K _{3, 2} or K_{5} | |

K _{3, 3} and K_{6} | |

K _{3, 3} or K_{5} | |

K _{2, 3} and K_{5} |

Question 61 Explanation:

**According to Kuratowski's theorem**a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).

**Refer**: https://en.wikipedia.org/wiki/Kuratowski%27s_theorem

Question 62 |

The number of colours required to properly colour the vertices of every planar graph is

2 | |

3 | |

4 | |

5 |

Question 62 Explanation:

- According to the 4-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color.
- Every planar graph is four-colorable.

Question 63 |

Maximum number of edges in a n-Node undirected graph without self loop is

N ^{2} | |

N(n-1) | |

N(n+1) | |

N(N-1)/2 |

Question 63 Explanation:

**Maximum number of edges in a undirected graph with n nodes ?**

In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N

**(N−1)/2.**

**Maximum number of edges in a directed graph with n nodes ?**

If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is

**N * (N - 1)**.

**Alternative :**

The maximum number of edges in an n node undirected graph G (n, e) without self-loops is present in a complete graph (Kn):

A complete graph is a graph with N vertices and an edge between every two vertices.

- There are no loops.
- Every 2 vertices share exactly one edge.

_{N}for a complete graph with N vertices.

**Example :**

Question 64 |

Cyclometric complexity of a flow graph G with n vertices and e edges is

V(G) = e+n–2 | |

V(G) = e–n+2 | |

V(G) = e+n+2 | |

V(G) = e–n–2 |

Question 64 Explanation:

Cyclomatic complexity is a software metric. It provides a quantitative measure of the logical complexity of a program.

Cyclomatic complexity provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

Cyclomatic complexity has a foundation in graph theory and is computed in one of three ways.

Cyclomatic complexity provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

Cyclomatic complexity has a foundation in graph theory and is computed in one of three ways.

- The number of regions correspond to the cyclomatic complexity.
- Cyclomatic complexity V(G) for a flow graph G, is defined as, V(G)=E-N+2
where

E=Number of flow graph edges

N=Number of flow graph nodes - Cyclomatic complexity V(G) for a flow graph G, is defined as, V(G)=P+1
where

P=Number of predicate nodes contained in flow graph G.

Question 65 |

How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components ?

M+N–C | |

M–N–C | |

M–N+C | |

M+N+C |

Question 65 Explanation:

- A spanning tree is a subgraph of the original graph, which connect all the vertexes that where originally connected. This means that removing an edge form a spanning tree, at least a couple of vertexes that were originally connected get disconnected. The definition of spanning tree does not only apply to fully connected graph. When applied to disconnected graph it often takes the name of spanning forest
- Spanning forest is nothing but a set of spanning trees, one for each connected component in the graph
- In the spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
- When there is only
**one**connected component in your`graph`

, the`spanning tree = spanning forest`

. - But when there are multiple
`connected components`

in your graph. For example in following picture we have**3**`connected components`

- So for each
`component`

, we will have a`spanning tree`

, and all**3**`spanning trees`

will constitute`spanning forest`

- For an spanning forest of a graph with N vertices and C connected components, Number of edges should be
**E=(N-C)**, but in the given graph in the question contains M edges. So to have spanning forest number of edges to be removed

= M- (N-C)

= M - N + C

Question 66 |

An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are

All of even degree | |

All of odd degree | |

Of any degree | |

Even in number |

Question 66 Explanation:

**An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are All of even degree.**

**Euler Graph :**

A given connected graph G is a Euler Graph if and only if all vertices of G are of

**even degree**.

**(OR)**

An Euler Graph is a connected graph that contains an Euler Circuit.

So option(A) is correct answer

Above graph is a connected graph and all its vertices are of even degree. So, it is an Euler graph.

Alternatively, the above graph contains an Euler circuit

**BACEDCB**, Therefore, it is an Euler graph.

Question 67 |

The minimum number of edges in a connected graph with ‘n’ vertices is equal to

N(n – 1) | |

N(n–1)/2 | |

N ^{2} | |

N – 1 |

Question 67 Explanation:

Connect Graph have minimum (n-1) edges and maximum n(n-1)/2 edges

**Maximum number of edges in a undirected graph with n nodes ?**In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N**(N−1)/2.****Maximum number of edges in a directed graph with n nodes ?**If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is**N * (N - 1)**.
There are 67 questions to complete.