Order plus size of $\tau$-critical graphs

Andras Gyarfas, Lehel Jeno

Let $G=(V,E)$ be a $\tau$-critical graph with $\tau (G)=t$. Erdős and Gallai proved that $|V|\le 2t$ and the bound $|E|\le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)$ was obtained by Erdős, Hajnal and Moon. We giv…