# 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.

• What have you done to think about this problem? Have you tried anything? Worked out any examples? Etc.? – 4-ier Aug 30 '18 at 8:00
• I tried to make a proof by contradiction. So... let the sum of degrees be bigger than 3n. If so, there is a vertex on a path that has degree bigger than 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 neighboors on a path, so its degree is smaller than n-p+2. Unfortunately those two didn't make contradiction. – Gaha Aug 30 '18 at 8:09
• @Gaha: include your attempt in the original post – Berci Aug 30 '18 at 8:18

Hint: Consider a vertex $v \not\in P$, at most how many vertices in $P$ that are adjacent to $v$? From that, in $\sum_{u \in P}\deg u$, at most how many times a vertex $v \not\in 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/3\rfloor}\le n?$