From 0a7de2c6c259fba4086479e3993318b5ac276f99 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 21 Jan 2008 19:06:33 +0100 Subject: [PATCH] A remark. --- mst.tex | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) diff --git a/mst.tex b/mst.tex index 58a8d5f..b1814c3 100644 --- a/mst.tex +++ b/mst.tex @@ -812,11 +812,21 @@ It suffices to show that the lemma holds for triangulations (if there are any edges missing, the situation can only get better) with at least 3 vertices. Since $G$ is planar, $\sum_v \deg(v) < 6n$. The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$, -hence by the same argument as in the previous proof, for at least $n/2$ +hence by the same argument as in the proof of the general lemma, for at least $n/2$ vertices~$v$ it holds that $d(v) < 6$, hence $\deg(v) \le 8$. \qed - +\rem +The constant~8 in the previous lemma is the best we can have. +Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them +lie on the outer face and have degrees at most~6, the remaining $n-\O(k)$ interior +vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$, +ignoring terms of order $\O(k)$. All interior triangles can be properly colored with +two colors, black and white. Now add a~new vertex inside each white face and connect +it to all three vertices on the boundary of that face. This adds $f/2 \approx n$ +vertices of degree~3 and increases degrees of the original $\approx n$ interior +vertices to~9, therefore about a half of the vertices of the new planar graph +has degree~9. \section{Using Fibonacci heaps} -- 2.39.5