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.
Best Answer
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).