Calculator Input
Choose an input mode, enter graph data, and submit. Results appear above this form under the header.
Example Data Table
This sample graph contains a four-vertex clique inside a six-vertex network.
| Graph | Vertices | Edge List | Maximum Clique | Clique Size | Density |
|---|---|---|---|---|---|
| Sample G | A, B, C, D, E, F | A-B, A-C, A-D, B-C, B-D, C-D, D-E, D-F, E-F | {A, B, C, D} | 4 | 0.6000 |
Formula Used
1) Clique Definition
A vertex subset C is a clique when every distinct pair of vertices in C shares an edge.
C is a clique if (u,v) ∈ E for all u,v ∈ C and u ≠ v
2) Maximum Clique Number
The calculator returns the largest clique size, usually written as the graph’s clique number.
ω(G) = max {|C| : C is a clique in G}
3) Graph Density
Density helps describe how connected the whole graph is compared with a complete graph of the same size.
Density = 2m / (n(n - 1))
4) Clique Edge Count
A clique with k vertices contains every possible edge among those vertices.
Edges inside clique = k(k - 1) / 2
5) Search Method
This tool uses an exact Bron–Kerbosch style search with pivoting and pruning. It does not rely on heuristics for the final answer.
How to Use This Calculator
- Choose Edge List or Adjacency Matrix.
- Enter optional vertex labels such as A,B,C,D.
- For edge lists, type one undirected edge per line.
- For matrices, provide a square zero-one adjacency matrix.
- Add a vertex count when you need isolated numbered vertices.
- Click Calculate Maximum Clique.
- Read the result summary above the form.
- Use the CSV and PDF buttons to export the result.
FAQs
1) What is a maximum clique?
A maximum clique is the largest vertex set in which every pair of vertices is directly connected by an edge.
2) What is the difference between maximal and maximum cliques?
A maximal clique cannot be extended by adding another adjacent vertex. A maximum clique is the largest among all maximal cliques.
3) Can I use an adjacency matrix instead of an edge list?
Yes. Enter a square zero-one matrix. Any positive off-diagonal value is treated as an undirected edge.
4) Why can large graphs take longer?
The maximum clique problem is NP-hard. Exact search time can grow rapidly as vertex count and graph complexity increase.
5) Does vertex order change the answer?
No. Vertex ordering may affect search speed, but it does not change the exact maximum clique returned.
6) Are isolated vertices allowed?
Yes. They remain part of the graph, but isolated vertices cannot join any clique larger than size one.
7) What does graph density mean here?
Density measures how many edges exist compared with the maximum possible number of edges in an undirected simple graph.
8) Is the reported clique exact or approximate?
It is exact. The search uses pruning for efficiency, but the final maximum clique is not estimated or guessed.