G is finite (this is the de Bruijn–Erdős theorem of de Bruijn & Erdős 1951). δ(G) ≥ k − 1, that is, every vertex is adjacent to at least k − 1 others.
G véges (ez a de Bruijn–Erdős-tétel: de Bruijn & Erdős 1951). δ(G) ≥ k − 1, tehát minden csúcs legalább k − 1 csúccsal szomszédos.