Vtyjkyuk

Let $G$ be a simple graph with $n$ vertices. Let $P$ be the shortest path between any two vertices. Prove that: $$sum_vin Pdeg(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 $frac3np$, 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: Consider a vertex $v notin P$, at most how many vertices in $P$ that are adjacent to $v$? From that, in $sum_u in Pdeg u$, at most how many times a vertex $v notin P$ (or $v in P$) is counted?

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/3rfloorle n?$