Prove that a sum of degrees in a path between two vertices is smaller than $3n$ Let $G$ be a simple graph with $n$ vertices. Let $P$ be the shortest path between any two vertices. Prove that: $$\sum_{v\in P}deg(v)\leq 3n$$
Let the sum of degrees be bigger than $3n$. If so, there is a vertex on a path that has degree bigger than $\frac{3n}{p}$, where $p$ is the size of a path. And we know that a vertex in a path can't have more than $2$ neighbors on a path, so its degree is smaller or equal $n-p+2$. Unfortunately those two don't make contradiction.
I think at least two non adjacent vertices (with $dist(x,y)>2$) on a path should have a common neighbor outside the path. This would make a contradiction with the path being the shortest. But I don't know how to show that.

Hint. Let $v_0,v_1,v_2,\dots,v_n$ be a path of minimum length from $v_0$ to $v_n.$ Can you show that $\deg v_0+\deg v_3+\deg v_6+\cdots+\deg v_{\lfloor n/3\rfloor}\le n?$
