Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n{2}^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with$$\ge \left(\frac{1}{2}+o(1)\right)n{2}^{n-1}$$many edges contains a $C_4$?

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

This is **not known**. In fact it is a well-known **Erdős open problem**.

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

2 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.