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.