Let $G=(V,E)$ be a $tau$-critical graph with $tau(G)=t$. ErdH{o}s and Gallai proved that $|V|leq 2t$ and the bound $|E|leq {t+1choose 2}$ was obtained by ErdH{o}s, Hajnal and Moon. We give here the sharp combined bound $|E|+|V|leq {t+2choose 2}$ and find all graphs with equality.
تحميل البحث