Undirected Graph

Question 1
Marks : +2 | -2
Pass Ratio : 100%
Which of the following graphs are isomorphic to each other?
fig 1 and fig 2
fig 2 and fig 3
fig 1 and fig 3
fig 1, fig 2 and fig 3
Explanation:
All three graphs are Complete graphs with 4 vertices.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
O(E*E)
O(V*V)
O(E)
O(V)
Explanation:
A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
All trees with n vertices consists of n-1 edges.
True
False
Explanation:
A trees is acyclic in nature.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
All paths and cyclic graphs are bipartite graphs.
True
False
Explanation:
Only paths and even cycles are bipartite graphs.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
In the given graph which edge should be removed to make it a Bipartite Graph?
A-C
B-E
C-D
D-E
Explanation:
The resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?
1
2
3
4
Explanation:
Euler’s Identity says V – E + R = 1+ number of connected components.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is ________
2((n*(n-1))/2)
2((n*(n+1))/2)
2((n-1)*(n-1))/2)
2((n*n)/2)
Explanation:
There can be at most, n*n edges in an undirected graph.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
How many of the following statements are correct?
1
2
3
4
Explanation:
Statements iii) and v) are correct.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
Number of vertices with odd degrees in a graph having a eulerian walk is ________
0
Can’t be predicted
2
either 0 or 2
Explanation:
If the start and end vertices for the path are same the answer would be 0 otherwise 2.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
n-2
n
2
0
Explanation:
Only the first and the last vertex would have degree 1, others would be of degree 2.