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 ?
A clique in a graph is a subset of vertices such that every two distinct vertices in the clique are adjacent. In simpler terms, a clique is a complete subgraph where each vertex connects directly to every other vertex in the subgraph. The task is to find all maximal cliques in the given graph. A maximal clique cannot be extended by including one more adjacent vertex, meaning it is not part of any larger clique.
Let's analyze the given graph:
From the image of the graph, we can identify the following cliques:
- Triangle \( \{a, b, g\} \): This is a clique because all vertices (a, b, g) are connected to each other.
- Triangle \( \{b, c, e\} \): This is a clique consisting of vertices b, c, and e.
- Triangle \( \{a, d, g\} \): This is a clique with vertices a, d, and g.
- Triangle \( \{d, e, f\} \): This forms a clique with vertices d, e, and f.
- Triangle \( \{c, e, f\} \): This is a clique of vertices c, e, and f.
Each triangle mentioned is a maximal clique, as adding another vertex to any of these subgraphs would break the complete connectivity required for a clique.
Therefore, the total number of cliques in the graph is 5.
This matches with option 5, confirming that this is the correct answer.
Important Questions from Graph Theory
Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
- Maintaining a graph in memory by means of its adjacency matrix is known as
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on plane is equal to_________.
- The number of possible rooted trees in a phylogeny of three species is ________.
Consider the following statements regarding graph theory :
1. Chord is that branch of the graph that does not belong to the particular tree.
2. Cut-set is a unique set with respect to a given tree of a connected graph containing one chord and all of the free branches contained in the free path formed between two vertices of the chord.
3. If M represents the number of branches and N the number of nodes, the minimum number of variables involved in analyzing a network is equal to $(M + N − 1)$.
Which of the above statements are not correct?
