# T1: A Simple Question on Ruzsa-Szemerédi Graphs

Question: Is there a graph in which each edge is in an induced matching? And the density of the graph can be very large.

Answer: There is one. Ruzsa-Szemerédi graph!

We say that a graph is an (r,t)-Ruzsa-Szemerédi graph if its edge set can be partitioned into \(t\) induced matchings, each of size \(r\).

So, every edge is in the matching! Oh, that is amazing.

\(\textbf{Lemma}\). For infinitely many integer \(N\), there are \((r,t)\)-Ruzsa-Szemerédi Graph on \(N\) vertices, where \(r = N/e^{\sqrt{\log N}}\) and \(t = N/3\).

The lower bound of maximum edges is \(n/e^{O(\sqrt{\log n})}\). This means that the average degree is \(n/e^{O(\sqrt{\log n})}\) (very large).