Is an Undirected Graph Determined by the Number of Cliques of Each Vertex Size?

The short answer is no. The number of cliques for each vertex size in an undirected graph does not necessarily determine the graph's isomorphism. Let's explore this concept with concrete examples and graphical illustrations to clarify this.

Example 1: Hexagon with Extra Paths

Consider the following three graphs constructed from a hexagon (ABCDEF), with an added extra path:

AGHD, where AG and HD are opposite vertices in the hexagon. AGHC, where AG and HC are vertices of distance 2 in the hexagon. AGHB, where AG and HB are contiguous vertices in the hexagon.

These three graphs have the same number of cliques for each vertex size:

No 3-cliques. No 2-cliques. Each graph has exactly 8 1-cliques (each vertex).

However, their structural differences lead to different cycle counts:

The graph with AGHD has three 6-cycles. The graph with AGHC has one 5-cycle, one 6-cycle, and one 7-cycle. The graph with AGBH has one 4-cycle, one 6-cycle, and one 8-cycle.

Since they are not isomorphic (i.e., they do not have the same structure), these illustrations demonstrate that the number of cliques does not uniquely determine the graph.

Example 2: Graphs with Three Triangles

Another example involves building a connected graph using three triangles (3-cliques) with specific connections. Consider the following construction:

Three triangles sharing a common edge. The third triangle can be attached at two different places to form two non-isomorphic graphs.

Both graphs have:

3 3-cliques. 8 2-cliques. 6 1-cliques (vertices).

The key difference lies in the degree of a single vertex:

Only one graph will have a vertex of degree 5.

This illustrates that while the number of cliques for each vertex size is similar, the shape and structure of the graph can differ, leading to non-isomorphic graphs.

Example 3: Trees with the Same Number of Vertices

Consider two different trees on N vertices. Both trees have N-1 edges and no cliques larger than 2-cliques. Despite these trees having the same number of vertices and edges, they can be non-isomorphic, as many trees exist with the same number of vertices but different structures. For example, consider a straight line of N vertices and a tree with a central node connected to N-1 leaves. Both have N-1 edges and no 3-cliques, yet they are clearly not isomorphic.

Conclusion

The number of cliques for each vertex size in an undirected graph is not sufficient to determine its isomorphism. Multiple graphs can have the same number of cliques while still being structurally distinct. This highlights the importance of considering multiple graph properties when analyzing graph isomorphism.

References

For further reading on graph theory and isomorphism, consider reading textbooks on discrete mathematics or graph theory, or exploring online resources such as Wikipedia articles on graph theory and graph isomorphism.