UGC NET Computer Science December 2019 | Question 86

Question 86

---

A clique in an undirected graph G = (V, E) is a subset V' ⊆ V of vertices, such that

1. 1. If (u,v)∈E then u∈ V' and v∈V'
2. 2. If (u,v)∈ E then u∈ V' or v∈V'
3. 3. Each pair of vertices in V' is connected by an edge
4. 4. All pairs of vertices in V' are not connected by an edge

Answer : 3. Each pair of vertices in V' is connected by an edge

Explanation

A clique in an undirected graph G = (V, E) is a subset V' ⊆ V of vertices, such that induced subgraph of G is a complete graph.

∴ In complete graph, each pair of vertices in V' is connected by an edge

So, option 3 is correct answer

Definition : A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph.

Reference : Clique (graph theory)

Previous	Next
UGC NET CS December 2019 - Question 85	UGC NET CS December 2019 - Question 87