Discrete Mathematics written test Questions & Answers 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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
Answer: b
Clarification: 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
Answer: c
Clarification: 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
Answer: b
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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.