Graph theory

Introduction

Graph data structures are among the most important and exciting topics to learn in computer science because of their usage in several real-world applications like Google Maps, Circuit Designing, etc.

Formally, A graph is a non-linear data structure containing nodes and links between them called edges. 

Questions

1. In an undirected graph, the probability of an edge between two vertices is ½. Suppose there is a graph of 8 vertices. What will be the expected number of 3-length unordered cycles?

1. ⅜
2. 2
3. 7
4. 9

Solution: C
Explanation: For forming a 3-length cycle, we need to select 3 vertices out of those 8 available vertices. This can be done in ⁸C₃ ways. And, for each different way, we have the probability that the edges may be connected or not. For the edges to form 3-length unordered cycles, all the chosen 3 vertices should be connected. For 3 vertices to be connected, the probability is (½) ^3. Therefore, the expected number of 3-length unordered cycles will be ⁸C₃*((½))^3 = 7.

2. In an undirected graph, which of the following statements are true?
A: The number of vertices with an odd degree is even.
B: The sum of degrees of all vertices is even.

1. A only
2. B only
3. Both A and B
4. Neither A and B

Solution: C
Explanation: When we add an edge in an undirected graph, the degrees of both the vertices through which the edge goes increase by 1. Therefore, the number of vertices with odd lengths is always even. Now, the sum of degrees of all vertices is 2*(number of edges), which is an even number. Therefore, both statements are true.

3. Given an undirected connected planar graph with 10 vertices and 15 edges, the number of bounded faces in any embedding of this graph on the plane is

1. 1
2. 2
3. 4
4. 6

Solution: D
Explanation: We know that all the graphs follow Euler's formula for planar graphs. Therefore, the equation v-e+f = 2 is followed by the above-given graph. Here, v=  10 and e= 15. Thus, the value of f is 6. 

4. Given a graph with 6 labeled vertices, the number of distinct cycles of length 4 is equal to

1. 14
2. 15
3. 450
4. 45

Solution: D
Explanation: Since the graph is complete, any 4 vertices can form a cycle. The different number of ways to choose 4 vertices out of 6 is ⁶C₄, which is equal to 15. With each set of 4 vertices, there can be 3 distinct cycles. Therefore, the answer is 15*3 = 45.

5. The chromatic number of a simple connected graph with n vertices and not containing any odd-length cycle is

1. 0
2. 1
3. 2
4. n-1

Solution: C
Explanation: The chromatic number of a simple connected graph is the number of colors required to color the graph so that no two adjacent vertices have the same color. 
A simple connected graph is a bipartite graph. Therefore, we can color it using 2 different colors.

6. Which statements among the given four are correct about simple connected undirected graphs with 3 or more vertices?

1. All the vertices have the same degree
2. At least 3 vertices have the same degree
3. At least 2 vertices have the same degree 
4. No two vertices have the same degree

Solution: C
Explanation: We know that, in a simple graph, there are no self-loops and parallel edges. Also, here the graph is connected. Therefore, no vertex has a degree equal to 0. Thus, all the vertices can have degrees from 1 to n-1. Since there are a total of n vertices, we can say that there must be at least vertices having the same degree.

7. If A is a non-planar graph with a minimum possible number of edges, then, A has

1. 12 edges and 6 vertices
2. 9 edges and 4 vertices
3. 9 edges and 6 vertices
4. 10 edges and 4 vertices

Solution: C
Explanation: The graphs with (10 edges and 5 vertices) and (9 edges and 6 vertices) are the minimum non-planar graphs. Out of these, the graph with 9 edges and 6 vertices has the minimum number of edges. Therefore, that is the answer.

8. What is the maximum number of edges in a bipartite graph containing 12 vertices?

1. 42
2. 15
3. 36
4. 12

Solution: C
Explanation: The bipartite graph will have the maximum number of edges in the case when the two colors contain 6 vertices each, and each of those 6 vertices of one color is connected to the 6 vertices of the other color. Therefore, the number of edges should be 6*6 = 36.

9. If there are n vertices and k connected components in forest B, then the number of edges is?

1. n-1 
2. n-k
3. n-k+1
4. ceil(n/k)

Solution: B
Explanation: According to the pigeonhole principle, each connected component will have n/k vertices. Thus, in each component, there will be a total of (n/k)-1 edges. And there are a total of k components. Therefore, the total number of edges will be k*((n/k)-1) = n-k.

10. You are given the following graph. The minimum number of different colors required to color this graph, so that no two adjacent vertices have the same color is:
 

1. 1
2. 2
3. 3
4. 4

Solution: D
Explanation: In the above graph, we can assign same color to vertex {1,2}, {3,4}, {5,7}, and {6,8}. Therefore, a total of 4 distinct colors will be required. 

11. Given a graph B containing n nodes and k different components. In what range should the number of components be in the resultant graph if we remove one vertex from it?

1. [k,n]
2. [k-1,k+1]
3. [k-1,n-1]
4. [k+1,n-k]

Solution: C
Explanation: The minimum case will lie when the vertex is itself a different connected component. Therefore, if we remove that vertex from the graph, it leaves k-1 components behind.

The maximum case will lie when the vertex is the one vertex disconnecting all components. In that case, its removal will leave n-1 components behind.

12. In a complete graph containing 6 vertices, the number of perfect matchings is?

1. 12
2. 15
3. 24
4. 36

Solution: B
Explanation: Here, for the first perfect matching, the number of options is 5. For second perfect matching, the number of options is 3, and for third perfect matching, the number of options is 1. Therefore, the total number of perfect matchings is 5*3*1 = 15.

13. A graph B is given, which satisfies |E|<=3*|V| - 6, where |E| is the number of edges and |V| is the number of vertices. If the minimum degree is defined as the minimum of degrees of all vertices, then the minimum degree of B can’t be

1. 4
2. 5
3. 3
4. 6

Solution: D

Explanation: Suppose the minimum degree of B is p, then B has a minimum of |V|*(p/2) edges. Also, it’s given that, |E|<=3*|V| - 6, i.e., |V|*(p/2)<=3*|V| - 6. 
If we check on the above options, for p = 6, |V|*(3)<=3*|V|-6 which implies 0<=-6 which is not true. Therefore, the minimum degree of B can’t be 6.

14. What is the maximum number of edges in an n-node undirected graph that doesn’t contain any self-loops?

1. n²
2. n*(n-1)/2
3. (n-1)
4. (n+1)*(n)/2

Solution: B

Explanation: All the edges between two different vertices are allowed in this case. Therefore, the answer would be “n choose 2” = n*(n-1)/2

15. For a connected planar graph having 10 vertices, given that, on each face, the number of edges is three, then the number of edges in the graph is

1. 15
2. 20
3. 24
4. 36

Solution: C
Explanation: Here, the graph is planar. Therefore, it follows the Euler's formula. Thus, v-e+f = 2. 
It’s given that the number of vertices is 10. And since the number of edges on the face is three, we can write that 2*e = 3*f as every edge is contained in 2 faces. Using the above two equations, we get e = 24.

Check out this problem - No of Spanning Trees in a Graph