Order plus size of $\tau$-critical graphs

Abstract

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 give here the sharp combined bound $|E|+|V|\le \left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$ and find all graphs with equality.