Tricky Discrete Mathematics Questions and Answers on “Complete and Connected Graphs”.
1. A bridge can not be a part of _______
a) a simple cycle
b) a tree
c) a clique with size ≥ 3 whose every edge is a bridge
d) a graph which contains cycles
Answer: a
Clarification: In a connected graph, a bridge is an edge whose removal disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle. A clique is any complete subgraph of a graph.
2. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
a) subgraph
b) tree
c) hamiltonian cycle
d) grid
Answer: b
Clarification: If all the edge weights of an undirected graph are positive, any subset of edges that connects all the vertices and has minimum total weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be exact.
3. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
a) Complete bipartite graph
b) Hamiltonian cycle
c) Regular graph
d) Euler graph
Answer: d
Clarification: In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.
4. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
a) 98
b) 13
c) 6
d) 34
Answer: c
Clarification: Edge set consists of edges from i to j using either 1) j = i+1 OR 2) j=3i. The trick to solving this question is to think in a reverse way. Instead of finding a path from 1 to 50, try to find a path from 100 to 1. The edge sequence with the minimum number of edges is 1 – 3 – 9 – 10 – 11 – 33 which consists of 6 edges.
5. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
a) 11
b) 14
c) 18
d) 19
Answer: c
Clarification: We know that, sum of degree of all the vertices = 2 * number of edges
2*7 + 5*2 + 6*x = 39*2
x=9
Number of vertices = 7 + 2 + 9 = 18.
6. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.
a) k-1
b) k2
c) 2k+3
d) k3+4
Answer: a
Clarification: This is possible with spanning trees since, a spanning tree with k nodes has k – 1 edges.
7. The minimum number of edges in a connected cyclic graph on n vertices is _____________
a) n – 1
b) n
c) 2n+3
d) n+1
Answer: b
Clarification: For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices. SO, the answer should be n minimum edges.
8. The maximum number of edges in a 8-node undirected graph without self loops is ____________
a) 45
b) 61
c) 28
d) 17
Answer: c
Clarification: In a graph of n vertices we can draw an edge from a vertex to n-1 vertex we will do it for n vertices and 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. Hence, 8*(8-1)/2 = 28 edges.
9. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
a) n-1 and n+1
b) v and k
c) k+1 and v-k
d) k-1 and v-1
Answer: d
Clarification: If a vertex is removed from the graph, lower bound: number of components decreased by one = k-1 (remove an isolated vertex which was a component) and upper bound: number of components = v-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 (v-1) vertices isolated making (v-1) components.
10. The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G can be ___________
a) n+2
b) 3n/2
c) n2
d) 2n
Answer: b
Clarification: n+1(subsets of size < 2 are all disconnected) (subsets of size >= 2 are all connected)+1(subset of size >= 2 are all connected)=n+2 is the number of connected components in G.