15
$\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.

  • 0
    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](https://en.wikipedia.org/wiki/Clique_%28graph_theory%29#Definitions) will be helpful.2016-01-29

3 Answers 3

17

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

5

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

  • 0
    @raphnguyen" A "pentagon will all vertices connected" is not clear to me. Do you mean, $K_5$, the complete graph on 5 vertices? A complete graph is always a clique. Also, note Austin Mohr's comment; double check whether "maximum clique" means "clique of largest possible size" or if it means "clique that contains any other clique".2011-09-04
0

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.