مسیر، دور و گراف تهی

در مسیر $P_n$ و دور $C_n$ هر رأس خودش و حداکثر دو همسایه‌اش را می‌پوشاند. رأس‌ها را سه‌تا‌سه‌تا پشت‌سر‌هم دسته کن و از هر دسته رأس وسط را بردار؛ اگر یک یا دو رأس ماند، یک رأس هم برای آن‌ها بردار. در گراف تهی رأس‌ها همسایه ندارند، پس همهٔ رأس‌ها لازم‌اند و $\gamma =n$.