1
$\begingroup$

This question already has an answer here:

I am reading up about Graph theory and the example it gives for a Clique Subgraph looks like this...

enter image description here

Now it states that the bottom graph is "obviously" the clique graph for the top. Is this because it is the smallest graph that can be made so all vertices are adjacent? Would, for example, a graph with 5 or 6 vertices need to leave some unconnected?

Also it mentions that a Clique is a "Maximal complete subgraph" but I thought subgraphs were supposed to contain the same edges. So why are there only 3 nodes with degrees greater than 2 but in the clique there are 4

$\endgroup$

marked as duplicate by N. F. Taussig, Ken, Cameron Buie, Mike Pierce, user91500 Aug 28 '15 at 8:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

It sounds like you are conflating the concepts of clique, maximal clique, and clique graph. A clique of a graph $G = (V, E)$ is a set $X \subseteq V$ such that every two vertices in $X$ are adjacent (connected by an edge.) A maximal clique of $G$ is a clique $X$ which is as big as possible (i.e. adding any vertex would violate the clique condition.)

The clique graph of $G$ is new graph $H = (V', E')$, defined as follows. The vertex set $V'$ is the set of maximal cliques of $G$. (Each vertex in the clique graph represents a whole clique in the original graph!) The edge set $E'$ is the set of pairs of maximal cliques $\{X, Y\}$ such that $X \cap Y \neq \varnothing$. (Two maximal cliques are connected by an edge if they share a vertex.)

The first graph depicted in your question has $4$ distinct maximal cliques, each of which is a triangle. (See image here.) Every two of these four cliques share at least one vertex. Hence, the clique graph of that first graph is $K_4$, the complete graph on $4$ vertices.

$\endgroup$
1
$\begingroup$

For the clique graph, the (maximal) cliques of the original graph are the vertices, and they are adjacent if the corresponding cliques share a vertex in the original graph.

In your example, the maximal cliques in the original graph are all of size 3, so the four $3$-cycles of the first graph are represented by the four vertices in the clique graph. Any two $3$-cycles of the original graph share at least one vertex, so the vertices of the clique graph are all adjacent.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.