This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Isomorphism in Graphs”.
1. A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).
a) 6k, 6k-1
b) 4k, 4k+1
c) k, k+2
d) 2k+1, k
View Answer
Explanation: By using invariant of isomorphism and property of edges of graph and its complement, we have: a) number of edges of isomorphic graphs must be the same.
b) number of edge of a graph + number of edges of complementary graph = Number of edges in Kn(complete graph), where n is the number of vertices in each of the 2 graphs which will be the same. So we know number of edges in Kn = n(n-1)/2. So number of edges of each of the above 2 graph(a graph and its complement) = n(n-1)/4. So this means the number of vertices in each of the 2 graphs should be of the form “4x” or “4x+1” for integral value of number of edges which is necessary. Hence the required answer is 4x or 4x+1 so that on doing modulo we get 0 which is the definition of congruence.
2. Every Isomorphic graph must have ________ representation.
a) cyclic
b) adjacency list
c) tree
d) adjacency matrix
View Answer
Explanation: A graph can exist in different forms having the same number of vertices, edges and also the same edge connectivity, such graphs are called isomorphic graphs. Two graphs G1 and G2 are said to be isomorphic if −> 1) their number of components (vertices and edges) are same and 2) their edge connectivity is retained. Isomorphic graphs must have adjacency matrix representation.
3. A cycle on n vertices is isomorphic to its complement. What is the value of n?
a) 5
b) 32
c) 17
d) 8
View Answer
Explanation: A cycle with n vertices has n edges. Number of edges in cycle = n and number of edges in its complement = (n*(n−1)/2) – n. To be isomorphism, both graphs should have equal number of edges. This gives, (n*(n-1)/2) – n = n
⇒ n = 5
4. How many perfect matchings are there in a complete graph of 10 vertices?
a) 60
b) 945
c) 756
d) 127
View Answer
Explanation: Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (exactly one appearance). So for n vertices perfect matching will have n/2 edges and there won’t be any perfect matching if n is odd. For n=10, we can choose the first edge in 10C2 = 45 ways, second in 8C2=28 ways, third in 6C2=15 ways and so on. So, the total number of ways 45*28*15*6*1=113400. But perfect matching being a set, order of elements is not important and the permutations 5! of the 5 edges are same only. So, total number of perfect matching is 113400/5! = 945.
5. A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)
a) Planner graph
b) Polyhedral graph
c) Homomorphic graph
d) Isomorphic graph
View Answer
Explanation: A simple connected planar graph is called a polyhedral graph if the degree of each vertex is(V) ≥ 3 such that deg(V) ≥ 3 ∀ V ∈ G and two conditions must satisfy i) 3|V| ≤ 2|E| and ii) 3|R| ≤ 2|E|.
6. A complete n-node graph Kn is planar if and only if _____________
a) n ≥ 6
b) n2 = n + 1
c) n ≤ 4
d) n + 3
View Answer
Explanation: Any graph with 4 or less vertices is planar, any graph with 8 or less edges is planar and a complete n-node graph Kn is planar if and only if n ≤ 4.
7. A graph is ______ if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
a) bipartite graph
b) planar graph
c) line graph
d) euler subgraph
View Answer
Explanation: A graph is known as planar graph if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
8. An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if ____________
a) f(u) and f(v) are contained in G but not contained in H
b) f(u) and f(v) are adjacent in H
c) f(u * v) = f(u) + f(v)
d) f(u) = f(u)2 + f(v)2
View Answer
Explanation: Two graphs G and H are said to be isomorphic to each other if there exist a one to one correspondence, say f between the vertex sets V(G) and V(H) and a one to one correspondence g between the edge sets E(G) and E(H) with the following conditions:-
(i) for every vertex u in G, there exists a vertex u’ in H such that u’=f(u) and vice versa.
(ii) for every edge uv in G, g(uv)=f(u)*f(v)=u’v’ is H.
9. What is the grade of a planar graph consisting of 8 vertices and 15 edges?
a) 30
b) 15
c) 45
d) 106
View Answer
Explanation: If G is a planar graph with n vertices and m edges then r(G) = 2m i.e. the grade or rank of G is equal to the twofold of the number of edges in G. So, the rank of the graph is 2*15=30 having 8 vertices and 15 edges.
10. A _______ is a graph with no homomorphism to any proper subgraph.
a) poset
b) core
c) walk
d) trail
View Answer
Explanation: A core can be defined as a graph that does not retract to any proper subgraph. Every graph G is homomorphically equivalent to a unique core called the core of G.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Discrete Mathematics Books
- Practice Information Technology MCQs
- Check BCA Books
- Apply for Computer Science Internship
- Apply for BCA Internship
