Guarantee existence of a 2-clique in a clique decomposition of Kn

158 Views Asked by At

In this discrete geometry course, a clique decomposition of a graph G is a set of pairwise disjoint complete subgraphs, each containing less than n vertices, whose union is G, and an n-clique is a complete subgraph with n vertices.

In order to finish a proof that I'm working on, I need to show that, for n>=3, a clique decomposition of K_n (the complete graph with n vertices) must contain at least one 2-clique. I found a way to show this for n>=8, but if I'd like to use a solution that works for all n>=3 so I don't need to prove case-by-case for n=3, 4, 5, 6, 7. Can anyone come up with a way to do this?

1

There are 1 best solutions below

0
On

For $n\ge 3$, a clique decomposition of $K_n$ (the complete graph with $n$ vertices) must contain at least one $2$-clique.

This is not true, any Steiner system $S(2,k,n)$ for $k\ge 3$ considered as a decomposition of $K_n$ into copies of $K_k$ is a counterexample.