Data-Communication
October 15, 2023GATE 2009
October 15, 2023UGC NET CS 2016 July- paper-2
Question 5
|
A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below?
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-54-26-300x129.png)
2
|
|
4
|
|
5
|
|
6
|
Question 5 Explanation:
Definition of clique is already given in question.
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step-1: b,c,e,f is complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-55-38.png)
Step-2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step-1: b,c,e,f is complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-55-38.png)
Step-2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-56-29.png)
Correct Answer: C
Question 5 Explanation:
Definition of clique is already given in question.
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step-1: b,c,e,f is complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-55-38.png)
Step-2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step-1: b,c,e,f is complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-55-38.png)
Step-2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
![](https://solutionsadda.in/wp-content/uploads/2019/03/Screenshot-from-2019-03-21-14-56-29.png)
Subscribe
Login
0 Comments