Açıklamada $4\times 4$ tahta için $8$ dama taşının yeterli olduğu bir örnek vermiştim. Biraz daha düşününce $7$ dama taşı ile de bu mümkün olmaktadır. Örnek durum şöyledir:
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \text{ } \\ \hline
\text{ } & \circ & \circ & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } \text{ } \\ \hline
\end{array}
Her $n$ pozitif tam sayısı için, gerekli olan minimum dama taşı sayısını hesaplamaya çalışmanın zorluğunu gmrmüş oluyoruz. Bulduğumuz bir değerin, minimum dama taşı sayısı olduğundan emin olmamız gerekir. Şimdi çizge teorisi ile çözümüne başlayalım.
İçine dama taşı koyduğumuz karelerin merkezlerini işaretleyelim ve bu noktaları bir çizgenin köşeleri olarak düşünelim. Ayrıca, içinde dama taşı bulunan ve ortak kenara sahip iki karenin merkezlerini birleştirelim. Bu şekilde bir çizge elde ederiz. Bu çizgenin kapsayıcı ağacı (spanning tree) $T$ olsun. $T$ nin köşe sayısına $m$ diyelim. Amacımız, $ m \geq \dfrac{n^2-3}{2}$ olduğunu göstermektir.
Tahtada, içinde dama taşı olmayan (boş) karelerin sayısı $b$ ile gösterelim.
$$ b + m = n^2 \tag{1}$$
dir. $T$ çizgesinde her noktanın derecesi en fazla $4$ olabilir. Çünkü o noktanın sağında, solunda, üstünde veya altında bir başka dama taşı olan komşu kareler bulunabilir. Böylece boş karelerin sayısını, dama taşı olan kareler yardımıyla sayabiliriz. Bir $v\in T$ köşesi için, $v$ ye komşu olan dolu karelerin sayısı $\deg(v)$ olduğundan, komşu boş karelerin sayısı en fazla $4 - \deg(v)$ olabilir. Böylece
$$ \sum_{v\in T} (4 - \deg(v)) \geq b \tag{2}$$ olur.
Ağaç çizgenin kenar sayısı özelliğini kullanırsak, $$ \sum_{v\in T} \deg(v) = 2|E| = 2(m-1) \tag{3}$$
elde ederiz. $(2), (3)$ bağıntılarını $(1)$ de yazarsak $4m - 2(m-1) + m \geq n^2 \implies 3m + 2 \geq n^2 $ olup
$$ m\geq \dfrac{n^2 - 2}{3} $$
sonucuna ulaşılır $\blacksquare$