Maximal and Maximum Cliques

First of all, all those 3-cliques you mentioned are indeed cliques.
As you said, a clique is a subgraph where all the nodes are connected to all the other nodes. So in your example, (3,4,5) is a clique, and so is (3,4,5,6), and so are (3) and (3,4) (which also answers some of your other questions).

Regarding maximum cliques, of course you could have more than 1 - for example, if you take the (3,4,5,6) from your graph, duplicate it to (3',4',5',6'), and connect 3 with 3', then you have 2 4-cliques in your graph, but no 5-cliques.

Also, any subgraph of a clique is also a clique, since every subgraph still satisfies the demand for all nodes being connected to all the other ones. For example in your graph, (3,4,5,6) is a 4-clique. Take any 3 nodes from there, and you shall get a 3-clique. Take 2, and you get a 2-clique. So in fact, not only every 4-clique has at least 1 3-clique in it, but it has exactly 4 3-cliques in it (that's 4C3).

Note, however, that sometimes cliques are defined as having 2 or more (or sometimes 3 or more) nodes, because anything smaller is a bit trivial, for lack of a better word.

Tags:

Graph Theory