16
$\begingroup$

enter image description here

EDIT
I am working on an exercise based on the image above and have picked the corresponding answers to describe the graph:

  • A maximum clique size in this graph is 4
  • (3,5,6) is a maximal clique in this graph
  • (1,2,7) is a maximal clique in this graph
  • The number of maximal 3-cliques in this graph is 6
  • (4,5,6) is a clique in this graph
  • Every graph with one or more nodes must have at least one clique
  • Every k-clique has (k * (k-1)) / 2 edges

The answers I left unchecked were:

  • Every graph has only ONE maximum clique
  • If the graph has a 4-clique, then it does not necessarily have a 3-clique

Do these answers seem right or where have I messed up in understanding the concept?



I am having trouble grasping the concept of graph theory.

By definition, a clique is a complete subgraph where each pair of vertices are connected. Would this mean that if I had a 4-clique containing smaller triangles of 3 vertices and 3 edges, would I could these smaller triangles as 3-cliques?? Or should I omit those subgraphs since they are part of the 4-clique.

Does every graph have only one maximum clique? Imagining it visually in my mind, I feel like it is possible to have more than one maximum clique.

Is there such thing as a 2-clique (just an edge) or should every clique form a closed shape?

I can't seem to draw an instance of a 4-clique that does not have a 3-clique, so it is safe to assume that every 4-clique has at least one 3-clique? How would I go about checking for something like this on a larger scale?

Sorry for the heap of questions, but my instructor's notes are hard to follow along with.

$\endgroup$
4
  • 5
    $\begingroup$ +1 to all... Three wonderful answers in 15 mins. M.SE is a wonderful thing. $\endgroup$
    – user12998
    Sep 4, 2011 at 4:56
  • 4
    $\begingroup$ (3,5,6) is not maximal, because (3,4,5,6) is a bigger clique containing it. The number of maximal 3-cliques is only 2 (namely, (1,2,7) and (1,2,3)). If a graph has a 4-clique, then it must have a 3-clique (choose any 3 vertices inside the 4-clique - they must all be connected). $\endgroup$
    – Austin Mohr
    Sep 4, 2011 at 5:17
  • $\begingroup$ Thanks Austin, I just read the description that you posted. $\endgroup$
    – raphnguyen
    Sep 4, 2011 at 5:18
  • $\begingroup$ To further extend Austin's comment, (1, 2, 3) and (1, 2, 7) can both be made NOT maximal cliques, just by adding an edge from 3 to 7. Then, neither of them will remain maximal. Also, I hope these definitions will be helpful. $\endgroup$
    – azam
    Jan 29, 2016 at 11:19

3 Answers 3

Reset to default
18
$\begingroup$

A $k$-clique is just any collection of $k$ vertices in which every possible edge is present. Thus, you are right to say, for example, a 4-clique contains many different 3-cliques and 2-cliques (the latter being just an edge).

For your other question, you may be confusing the words "maximum" and "maximal". To appreciate the difference, consider a graph that is the disjoint union of a 3-clique and two 4-cliques (so the graph has three components).

Both of the 4-cliques are maximum-sized cliques in the graph, since they are the largest cliques you can find anywhere in the graph.

A clique is maximal if it cannot be made any larger in that particular graph. In our example, the three components are each maximal cliques. As you said earlier, the 4-cliques contain many 3-cliques within them. These "subcliques" are not maximal, since they can be made larger (in particular, they can be extended to the 4-clique containing them).

Notice that the 3-clique component is maximal (it cannot be made any larger with vertices in our graph) but not maximum (it is not a largest clique in the graph).

$\endgroup$
1
  • $\begingroup$ Great explanation. Thank you!! $\endgroup$
    – shakhawat
    Jan 20, 2019 at 1:07
5
$\begingroup$

A clique is, as you say, an induced subgraph in which every vertex is connected to every other vertex. Cliques may be contained in one another: in fact, every subgraph of a clique is necessarily itself a clique. Nothing wrong or problematic with that. So if you have a 4-clique, then each of its four subgraphs with three vertices are cliques as well.

No, not every graph has a unique maximum clique. For example, take two triangles and connect one vertex of one of them to another vertex of the other. No set of four vertices are mutually connected, so there are no 4-cliques in that graph; the two triangles are both maximal cliques, and there is no single "largest clique".

2-cliques make sense, but they are the trivial case of cliques (uninteresting).

$\endgroup$
11
  • $\begingroup$ Thanks, Arturo. Would the maximum clique of the two triangles you described be a 3-clique? $\endgroup$
    – raphnguyen
    Sep 4, 2011 at 5:03
  • 1
    $\begingroup$ @raphnguyen: "Maximum" means that it is larger than any other clique; "maximal" means that no clique is stricly larger. The two traingle graph I described has no maximum clique (like I noted). Each of the triangles are maximal cliques of that graph. Moreover, generally a "maximal clique" is not merely a clique such that no clique has larger size, but rather is a clique that is not properly contained in any other clique; so a graph may have several maximal cliques, and maximal cliques may be of different sizes. $\endgroup$
    – Arturo Magidin
    Sep 4, 2011 at 5:04
  • $\begingroup$ I think I understand now. I have edited my original post with a problem that I am working on. The maximum clique of this graph should be 4, since it is larger than all other cliques in the graph? Should my answer for maximal cliques have been 2 instead of 6, since the 3-cliques within the 4-clique can be made into a bigger clique? $\endgroup$
    – raphnguyen
    Sep 4, 2011 at 5:13
  • $\begingroup$ @raphnguyen: Again: are you talking about the maximum size of a clique (which would be number), or about a "maximum clique" (which should not be simply a number, it should be a clique)? There is a unique maximum size of a clique in any finite graph, but there need not be any maximum cliques. $\endgroup$
    – Arturo Magidin
    Sep 4, 2011 at 5:18
  • $\begingroup$ @raphnguyen: (3,5,6) is not a maximal clique in the graph you have. It is properly contained in the clique defined by the vertices 3, 4, 5, and 6. (1,2,3), on the other hand, is a maximal clique. And any graph with a 4-clique must have a 3-clique: in fact, it must have at least four 4-cliques. $\endgroup$
    – Arturo Magidin
    Sep 4, 2011 at 5:21
0
$\begingroup$

Taking the Wikipedia definition, "A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two." two vertices that are connected by an edge form a clique. If you have any clique, any subset of the vertices form a clique, so a 4-clique will include four different 3-cliques. It is certainly possible to have more than one maximal clique. For example, draw two triangles (which will each form a clique). If you want a connected graph with two maximal cliques, connect a vertex of one triangle to a vertex of the other.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .