I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$.
The proof is made by contradiction where repeatedly any node from $G$ of degree at most $\lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $G'$ of $G$ of minimum degree more than $\lceil n^\frac{1}{k}\rceil$.
The conclusion is that $G'$ must have girth at most $2k$ and therefore also $G$, which is a contradiction.

I don't understand the conclusion: Why must $G'$ have girth at most $2k$? Why is it not possible that $G$ has girth more than $2k$ and minimum degree more than $\lceil n^\frac{1}{k}\rceil$?

I don't really see an answer to this question, so I would be very grateful if someone can help me.


1 Answer 1


Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N_1 > \lceil n^{1/k} \rceil$ neighbors. Each neighbor of $v$ has more than $\lceil n^{1/k} \rceil$ neighbors, and at least $\lceil n^{1/k} \rceil$ of them are different from $v$. The neighbors of different neighbors are all different, since otherwise $G'$ would have a 4-cycle. Denoting by $N_2$ the number of nodes at distance 2 from $v$, we have $N_2 \geq \lceil n^{1/k} \rceil N_1$. Continuing this way, we have $N_\ell \geq \lceil n^{1/k} \rceil N_{\ell-1}$ for all $\ell \leq k$ (here you use the lower bound on the girth; details left to you). In total, we get $N_k > \lceil n^{1/k} \rceil^k \geq n$, which is impossible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.