6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What have you done to think about this problem? Have you tried anything? Worked out any examples? Etc.? $\endgroup$ – 4-ier Aug 30 '18 at 8:00
  • $\begingroup$ 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. $\endgroup$ – Gaha Aug 30 '18 at 8:09
  • $\begingroup$ @Gaha: include your attempt in the original post $\endgroup$ – Berci Aug 30 '18 at 8:18
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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