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…
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?
Vertices: a, b, c, d, e, f, g
Edges: a-b, b-c, a-d, d-e, e-f, c-f, b-e, a-g, b-g, d-g, e-g, b-f, c-e
(In the figure a, b, c are on the top row, d, e, f on the bottom row, g is where the diagonals a-e and b-d cross; the diagonals b-f and c-e cross without a vertex.)
Show answerHide answer
Correct answer: (C) 5
Explanation
A clique is a maximal complete subgraph (every vertex connected to all other vertices in the subgraph). Such subgraphs are: (i) {b, c, e, f} (ii) {a, d, g} (iii) {a, b, g} (iv) {b, e, g} (v) {d, e, g}. There are 5 cliques.