Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Questions
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Graph theory

Author Shreya Deep
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 7
  3. 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 8C3 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 8C3*((½))^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 6C4, 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. n2
  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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What is a graph?
    A graph is a mathematical representation of a network, and it describes the relationship between lines and points.
     
  2. What does graph theory teach us?
    Graph theory is the study of relationships. Graph theory is a helpful tool for quantifying and simplifying the various moving aspects of dynamic systems, given a set of nodes and connections that can abstract anything from city plans to computer data.
     
  3. What are the properties of graph theory?
    A graph is a data structure made up of nodes and edges that are non-linear. The edges are lines or arcs that connect any two nodes in the graph, and the nodes are also known as vertices.
     
  4. What is the fundamental difference between a tree and a graph?
    tree is a special kind of graph that contains no cycles. So, every tree is a graph, but all graphs are not trees.
     
  5. What are the real-life applications of graphs? 
    Graphs represent social groups like in facebook's graph API, in making knowledge graphs, in path optimization algorithms for finding the shortest path between points, in GPS navigation systems, and chemistry.

Key Takeaways

We discussed some of the GATE previous years asked problems on graphs here in this article. You can look for more similar articles on graph theory. 

Problems related to graphs are asked during various coding contests as well as placements tests.

Related articles:


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

To practice and learn more about such topics, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and an overview of interview experiences of various product-based companies.

Happy Coding!

Previous article
Numerical methods and calculus- Part 2
Next article
Combinatorics
Live masterclass