GraphTheory
Question 1 
maximum of n and d  
n + d  
nd  
nd / 2 
d * n = 2 * E
∴ E = d*n/2
Question 2 
a, c, d  
a, b, d  
b, c, d  
a, b, c 
The graph has (a, b, c) as a strongly connected component.
Question 3 
e  
e/2  
e^{2}  
2 e 
Handshaking theorem states that the sum of degrees of the vertices of a graph is twice the number of edges.
If G=(V,E) be a graph with E edges,then
Σ deg_{G}(V) = 2E
This theorem applies even if multiple edges and loops are present.
Since the given graph is undirected, every edge contributes as twice in sum of degrees. So the sum of degrees is 2e.
Question 4 
same degree  
even degree  
odd degree  
different degree 
Proof:
→ Let G(V, E) be an Euler graph. Thus G contains an Euler line Z, which is a closed walk.
→ Let this walk start and end at the vertex u ∈ V. Since each visit of Z to an intermediate vertex v of Z contributes two to the degree of v and since Z traverses each edge exactly once, d(v) is even for every such vertex.
→ Each intermediate visit to u contributes two to the degree of u, and also the initial and ﬁnal edges of Z contribute one each to the degree of u. So the degree d(u) of u is also even.
Question 5 
n^{2}  
n(n1)/2  
n1  
n(n+1)/2 
Question 6 
Multigraph  
Non regular graph  
Regular graph  
Complete graph 
Question 7 
Path  
Walk  
Tree  
Circuit 
Let G be a graph and let there be exactly one path between every pair of vertices in G. So G is connected. Now G has no cycles, because if G contains a cycle, say between vertices u and v, then there are two distinct paths between u and v, which is a contradiction. Thus G is connected and is without cycles, therefore it is a tree.
A tree is a minimally connected graph i.e. removing a single edge will disconnect the graph. A tree with n vertices has n−1 edges and only one path exists between every pair of vertices.
Question 8 
n edges  
nk edges  
(n − k)(n − k + 1) edges  
(n − k)(n − k + 1)/2 edges 
So, G has maximum number of edges if each component is a complete graph.
Hence, the maximum possible number of edges in the graph G is:
And in every case, (n − k)(n − k + 1)/2 will be greater than or equal to the above expression.
So, at maximum, there can be (n − k)(n − k + 1)/2 edges in a simple graph with n vertices and k components.
Question 9 
k and n  
k1 and k+1  
k1 and n1  
k+1 and nk 
→ If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components
Question 10 
(v+1)−k  
(v+1)/2 −k  
v−k  
v+k 
→ Suppose, if each vertex is a component, then k=v, then there will not be any edges among them. So, vk= 0 edges.
Method2:
→ According to pigeonhole principle, every component have v/k vertices.
→ Every component there will be (v/k)1 edges.
→ Total k components and edges= k*((v/k)1)
= v–k
Question 11 
n * (n1) / 2  
n * (n+1) / 2  
n^{2}  
n * (n+1) 
Question 12 
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 13 
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 
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 14 
No bridges  
{d,e}  
{c,d}  
{c,d} and {c,f} 
Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
A graph is said to be bridgeless or isthmusfree if it contains no bridges.
If we remove {d,e} edge then there is no way to reach e and the graph is disconnected.
The removal of edges {c,d} and {c,f} makes graph disconnect but this forms a cycle.
Question 15 
It has 7 vertices  
It is evenvalent(all vertices have even valence)  
It is not connected  
It does not have a Euler circuit 
Important Properties:
→ An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.
→ An undirected graph can be decomposed into edgedisjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edgedisjoint cycles and its nonzerodegree vertices belong to a single connected component.
→ An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.
→ A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edgedisjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.
→ A directed graph has an Eulerian trail if and only if at most one vertex has (outdegree) − (indegree) = 1, at most one vertex has (indegree) − (outdegree) = 1, every other vertex has equal indegree and outdegree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph
Question 16 
ABCDCFDEFAEA  
AEDCBAF  
AEFDCBA  
AFCDEBA 
Here, Option A: A,F and E are repeated several times.
Option B: It is not a cycle. It means, not closed walk
Option C: It is closed walk and all vertex traversed. So this is final answer.
Option D: It’s not a closed walk.
Question 17 
e<=n  
e<=2n  
e<=en  
None of the option 
v − e + f = 2.
→ For a simple, connected, planar graph with v vertices and e edges and faces, the following simple conditions hold for v ≥ 3:
Theorem 1. e ≤ 3v − 6;
Theorem 2. If there are no cycles of length 3, then e ≤ 2v − 4.
Theorem 3. f ≤ 2v − 4.
Theorem (The handshaking theorem):
Let G be an undirected graph (or multigraph) with V vertices and N edges. Then
Exercise:
Suppose a simple graph has 15 edges, 3 vertices of degree 4, and all others of degree 3. How many vertices does the graph have?
3*4+(x3)*3=30
Question 18 
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 nonempty 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 
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.
Question 19 
The Kcoloring of an undirected graph G = (V, E) is a function
C: V ➝ {0, 1, ......, K1} 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 2colorable
 
G is bipartite

• A cycle of length n ≥ 3 is 2chromatic if n is even and 3chromatic if n is odd.
• A graph is bicolourable (2chromatic) if and only if it has no odd cycles.
• A nonempty graph G is bicolourable if and only if G is bipartite
Question 20 
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(n1)(n2) + 2
Choose the correct answer for the code given below:
Code:(i) and (iii) only
 
(ii) and (iii) only
 
(iii) only
 
(ii) only 
→ Dirac's theorem on Hamiltonian cycles, the statement that an nvertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
→ Dirac's theorem on chordal graphs, the characterization of chordal graphs as graphs in which all minimal separators are cliques.
→ Dirac's theorem on cycles in kconnected graphs, the result that for every set of k vertices in a kvertexconnected graph there exists a cycle that passes through all the vertices in the set.
Question 21 
n1  
bn  
bn+1  
independent of "the number of nodes 
● A loop is said to be independent if it contains at least one branch which is not a part of any other independent loop.
● A network with ‘b’ branches, ‘n’ nodes and ‘L’ independent loops will satisfy the fundamental theorem of network topology.
b=L+n−1
L=b−n+1
Question 22 
Zero  
One  
n1  
n/2 
● A circuit in such a tree is impossible (unless you have some other data structure as well such as a linked list or you just program the tree so badly it ends up with circuits).
Question 23 
2chromatic  
(n/2) chromatic  
(n1) chromatic  
nChromatic 
Question 24 
2  
3  
4  
n2⌈(n/2)⌉+2 
Question 25 
3  
4  
5  
6 
‘v’ is number of vertices and ‘e’ is number of edges
‘f’ is number of faces including bounded and unbounded
10  15 + f = 2
f = 7
There is always one unbounded face, so the number of bounded faces = 6
Question 26 
E  
2E  
V  
2V 
Suppose a graph has n vertices with degrees d _{1} , d _{2} , d_{ 3} , ..., d_{ n}.
Add together all degrees to get a new number
d _{1} + d _{2} + d_{ 3} + . .. + d_{ n} = D _{v} . Then D_{ v} = 2 e .
In words, for any graph the sum of the degrees of the vertices equals twice the number of edges.
Question 27 
Euler circuit  
Hamiltonian path  
Euler Path  
Hamiltonian Circuit 
● An Euler path is a path that uses every edge of a graph exactly once. An Euler circuit is a circuit that uses every edge of a graph exactly once.
● An Euler path starts and ends at different vertices.
● An Euler circuit starts and ends at the same vertex.
Question 28 
(a,b)(e,f)  
(a,b),(a,c)  
(c,d)(d,h)  
(a,b) 
● Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
● The removal of edges (a,b) and (e,f) makes graph disconnected.
Question 29 
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 
An Euler path in G is a simple path containing every edge of G exactly once.
An Euler path starts and ends at different vertices.
An Euler circuit starts and ends at the same vertex.
Question 30 
5  
6  
7  
8 
Where V is the number of vertices, E is the number of edges, and R is the number of regions.
R=2V+E=28+13=7
Question 31 
6  
8  
9  
13 
● Where V is the number of vertices, E is the number of edges, and R is the number of regions.
● R=2V+E=213+19=8
● We can also term region as face
Question 32 
28  
48  
20  
None of the option 
So, we can construct 5*8 = 40 diagonals.
But we have constructed each diagonal twice, once from each of its ends. Thus there are 20 diagonals in a regular octagon.
Question 33 
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 
For any(connected) planar graph with v vertices, e edges and faces, we have
V  E + F = 2
= 4  E + 4 =2
E = 4  2 + 4
E = 6
Question 34 
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 
A graph G is dual if and only if G is a ___
Euler graph
 
Regular graph  
Complete graph  
Planar graph

→ The correspondence between edges of G and those of G* is as follows:
if e∈E(G) lies on the boundaries of faces X and Y, then the endpts of the dual edge e*∈(G*) are the vertices x and y that represent faces X and Y of G.
Question 36 
What is the chromatic number of an nvertex simple connected graph, which does NOT contain any oddlength cycle?
N  
N1  
2  
3 
→ A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 37 
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 even
Neither (i) nor (ii)
 
Both (i) and (ii)  
Only (ii)  
Only (i)

True: Sum of degrees of all the vertices is always even.
Question 38 
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 
1. V(G1) = V(G2)
2. E(G1) = E(G2)
3. Degree sequences of G1 and G2 are same.
4. If the vertices {V1, V2, ... Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2), … f(Vk)} should form a cycle of length K in G2.
→ Graph G and H are having same number of vertices and edges. So, it satisfied first rule.
→ u1 degree 2, u2 degree 3, u3 degree 3, u4 degree 2, u5 degree 3, u6 degree 3.
→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.
→ But it violates the property of number of cycles. The number of cycles are not same.
Question 39 
Maximum of n,d  
n+d  
nd  
nd/2 
d*n = 2*E
∴ E = (d*n)/2
Question 40 
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 
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 
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. 
Step1: G1 have odd number of vertices. So, it is not euler circuit.
Step2: G2 also have odd number of vertices. So, it not euler circuit.
Question 43 
14, 14  
16, 14  
16, 4  
14, 4 
=n ^{(n2)}
= 4^{ 2}
=16
Step2: Given Bipartite graph K_{ 2,2} . To find number of spanning tree in a bipartite graph K _{m,n} having standard formula is m^{ (n1)} * n^{ (m1)} .
m=2 and n=2
= 2 ^{(21)} * 2^{ (21)}
= 2 * 2
= 4
Question 44 
2  
4  
5  
6 
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step1: b,c,e,f is complete graph.
Step2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
Question 45 
(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 
(b)TRUE: 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)TRUE: A complete graph (K _{n} ) has a Hamilton Circuit whenever n ≥ 3. (d) FALSE: A cycle over six vertices (C_{ 6} ) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Question 46 
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} ) 
→ The two sets U and V may be thought of as a coloring of the graph with two colors.
Option A: FALSE because V _{5} , V_{ 7} and V_{ 3} are adjacent. So, it not not bipartite graph.
OptionB FALSE because V _{5} , V_{ 6} and V_{ 2} are adjacent. So, it not not bipartite graph.
OptionC TRUE because it follows properties of bipartied and no two colours are adjacent.
OptionD FALSE because because V _{4} , V_{ 6} and V_{ 8} are adjacent. So, it not not bipartite graph.
Question 47 
(a)
(b)
(c)
(a) and (b)  
(b) and (c)  
(a) and (c)  
(a), (b) and (c) 
Question 48 
(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) 
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edgedisjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edgedisjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
Question 49 
(i) 1, 2, 3, 4, 5
(ii) 3, 4, 5, 6, 7
(iii) 1, 4, 5, 8, 6
(iv) 3, 4, 5, 6
then
(i) and (ii)  
(iii) and (iv)  
(iii) and (ii)  
(ii) and (iv) 
1. Sum of degrees of the vertices of a graph should be even.
2. Sum of degrees of the vertices of a graph is equal to twice the number of edges.
Statement(i) is violating property1.
= 1+2+3+4+5
= 15 is odd number.
Statement(ii) is violating property1.
= 3+4+5+6+7
= 25 is odd number.
Statement(iii) is violating property1.
= 1+4+5+8+6
= 24 is even number
Statement(iv) is violating property1
= 3+4+5+6
= 18 is even number
Question 50 
T is a tree  
T contains no cycles  
Every pairs of vertices in T is connected by exactly one path  
All of these 
Step1:
n= number of vertices
n1 = number of edges
Example: n=5 vertices and n1=4 edges
Step2: The above graph T won’t have cycle then we are calling as tree. Here, every pairs of vertices in T is connected by exactly one path.
Note: The above properties is nothing but minimum spanning tree properties.
Question 51 
N (N−1)  
2N−1  
N−1  
N(N−1)/2 
Question 52 
2N1  
N ^{N1}  
N ^{N2}  
2N+1 
Example:
Formula to find total number of spanning trees are N ^{N2}
=5 ^{52}
=5 ^{3}
=125
Question 53 
5  
n3  
20  
11 
Here, they are clearly mentioned that “certain tree”
The tree contain maximum n1 edges. Here, ‘n’ is number of vertices.
→ According to the handshaking lemma “sum of degrees of all vertices=2e”.
→ Two vertices of degree 4, we can write into (2*4)
→ One vertex of degree 3, we can write into (1*3)
→ One vertex of degree 2, we can write into (1*2).
→ Other vertices(X) have degree 1, we can write into (X*1)
Step1: (2*4)+(1*3)+(1*2)+(X*1)
=2(X+41) [Note: ‘X’ value is not given ]
X=7
Step2: To find total number of vertices, we are adding X+4 because they already given 4 vertices.
=X+4
=7+4
=11
Method2:
Draw according to given constraints but it not suitable for very big trees
B, C, E, F, H, I, J degree = 1
D degree = 2
A degree = 4
K degree = 4
G degree = 3
Question 54 
This graph is a __________.
Complete Graph  
Bipartite Graph  
Hamiltonian Graph  
All of the above 
OptionB: It is not Bipartite Graph because it takes more than 2 colours. Bipartite Graph have exactly 2 colours.
OptionC: Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.
Hence, OptionC is correct answer.
Question 55 
S 1 : A solution is a subtree that has a goal node at every leaf.
S 2 : OR nodes are analogous to the branching in a deterministic environment
S 3 : AND nodes are analogous to the branching in a nondeterministic 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 
● A solution in an ANDOR tree is a sub tree whose leaves are included in the goal set
Question 56 
G has no cycles of odd length  
G has cycle of odd length  
G is 2colorable  
G is bipartite 
● A cycle of length n ≥ 3 is 2chromatic if n is even and 3chromatic if n is odd.
● A graph is bicolourable (2chromatic) if and only if it has no odd cycles.
● A nonempty graph G is bicolourable if and only if G is bipartite
Question 57 
(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 
→ Dirac's theorem on chordal graphs, the characterization of chordal graphs as graphs in which all minimal separators are cliques
→ Dirac's theorem on cycles in kconnected graphs, the result that for every set of k vertices in a kvertexconnected graph there exists a cycle that passes through all the vertices in the set
Question 58 
→The same number of vertices, edges and degrees for corresponding vertices.
→The same number of connected components,loops and parallel edges.
The above graph each vertex having degree 3 and total number of vertices are 8. Total number of edges are 12.
OptionA: Vertex v_{5} having degree 4. So, it is not isomorphic graph.
OptionB: Vertex v_{6} having degree 4. So, it is not isomorphic graph.
OptionC: Every vertex having degree 3 and total number of edges and vertices are 12 and 8.
So, it is isomorphic.
OptionD: Vertex v_{6} having degree 4. So, it is not isomorphic graph.
Question 59 
m = 3, n = 2  
m = 2, n = 3  
m = n ≥ 2  
m = n ≥ 3 
Question 60 
Where V and E are the number of vertices and edges in graph respectively.
(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) 
→ Kruskal's algorithm is a minimumspanningtree algorithm which finds an edge of the least possible weight that connects any two trees in the forest and time complexity is O(E log E)
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v in the ordering Θ(V + E)
→ Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices
Question 61 
2451  
4950  
4851  
9900 
 Undirected graph G with 100 nodes.
 Maximum number of edges to be included in G so that the graph is not connected is ?
Step1: As per the above description, it is simple undirected graph.
For simple graph using formula standard formula is ((n1)*(n2))/2
Step2: Here, n=100
n1=99
n2=98
=((n1)(n2))/2
= (99*98)/2
= 4851
Note: The simple graph won’t have parallel edges and self loops.
Question 62 
(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 
Tree properties:
→A graph in which there is a unique path between every pair of vertices is a tree.
→A connected graph with e = v – 1 is a tree.
→A graph with e = v – 1 that has no circuit is a tree.
Question 63 
(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 
Simple graph properties:
→If a graph is connected then e≥n1.
→If a graph has more than e>((n1)(n2)) / 2 then it is connected.
→The n vertex graph with the maximal number of edges that is still disconnected is a K_{n1}
→A complete graph K_{n1} with n1 vertices ((n1)(n2)) / 2 edges.
→Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an ‘n’ vertex graph is (((n−1)(n−2)) / 2)+1
Question 64 
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 65 
2  
3  
4  
5 
→ The sufficient number of colors in worst case is 4 colors for any planar graph.
Question 66 
n^{2}  
n(n1)  
n(n+1)  
n(n1)/2 
Question 67 
V(G) = e+n–2  
V(G) = e–n+2  
V(G) = e+n+2  
V(G) = e–n–2 
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=EN+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 68 
M+N–C  
M–N–C  
M–N+C  
M+N+C 
→ 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.
→ In spanning forest, we will use multiple trees to represent a path through the graph.
→ Consider the below example
Number of components(C)=3
Number of vertices(N)=9
Number of Edges(M)=8
By removing two edges, we can make spanning forest in the above graph.
The number of edges can be removed to make spanning forest is MN+C=89+3=2
So option C is correct.
Question 69 
all of even degree  
all of odd degree  
of any degree  
even in number 
→ Eulerian circuit (or) Euler tour in an undirected graph is a cycle that uses each edge exactly once.
Question 70 
n(n – 1)  
n(n–1)/2  
n^{2}  
n – 1 
Question 71 
S2 : My professor teaches maths, electronics and computer science.
S3 : I have a student of maths.
S4 : Algorithm is a part of computer science.
S5 : Maths students know computer science.
What would be the chromatic number of a graph, vertices of which are the actors/entities that are involved in the sentences S1 to S5 and edgesto represent the associations/relationships amongst the entities/actors as expressed in the sentences S1 to S5 above ?
2  
3  
4  
None of these 
Question 72 
3  
4  
5  
6 
n=4
= 4(43)/2
= (4*3)/2
= 12/2
= 6
Question 73 
(i) G is a tree
(ii) There is at least one path between any two distinct vertices of G
(iii) G contains no cycles and has (n1) edges
(iv) G has n edges
(i) and (ii)  
(i) and (iii)  
(i) and (iv)  
(ii) and (iii) 
OptionB: TRUE because there is at least one path between any two distinct vertices of G. otherwise we are no calling as undirected graph.
OptionC: TRUE. If G contains no cycles and has (n1) edges.
OptionD: FALSE
Question 74 
n  
n(n – 1)/2  
n(n + 1)/2  
n^{2}/2 
Ex:
n=5 and complete graph
Using formula to find number of edges is n(n1)/2
=5*(51)/2
=(5*4)/2
=10
Question 75 
3 edges  
4 edges  
7 edges  
12 edges 
Total number of vertices= n + m
Total number of edges= m*n
Example:
Question 76 
n(n1)  
n(n1)/2  
n^{2}  
2n1 