100 spanning trees for graph G - prove existent of vertex v with degree at least 200

Question

In not directed and connected graph $ G=(V,E) $ there are $100$ spanning trees $ T_1,T_2,...T_{100} $.

Vertex $v$ in tree $T_i$ is signed $ d(v,T_i)$ for $ i=1,2,...100 $.

I need to prove the existent of vertex $v$ which its degree's sum in $100$ trees ($ \sum_{i=1}^{100} d(v,T_i) $) is smaller than $200$, and the existent of vertex $v$ which its degree's sum in $100$ trees is at least $200$.

$ d(v,T_i)$ is the vertex's degree in the $i$'s tree ($T_i$)

Thanks!

Answer 1

So we have, by handshake lemma: $$\sum _{v\in V(G)}d(v,T_i) =2n-2$$ for each $T_i$.

So $$\sum _{i=1}^{100}\Big(\sum _{v\in V(G)}d(v,T_i)\Big) =100(2n-2)$$

$$\sum _{v\in V(G)}\Big(\underbrace{\sum _{i=1}^{100} d(v,T_i)}_{d_v}\Big) =100(2n-2)$$

Let $d=\min\{d_v;\;v\in V(G)\}$ then $$n\cdot d= \sum _{v\in V(G)}d \leq 100(2n-2)$$

so $$d\leq 200{n-1\over n} <200$$

---

And you can do similary for $D=\max\{d_v;\;v\in V(G)\}$