Probar que la suma de grados en un camino entre dos vértices es menor que $3n$

Question

Deje que $G$ ser un simple gráfico con $n$ vértices. Que $P$ ser el camino más corto entre dos vértices cualesquiera. Demuéstralo: $$ \sum_ {v \in P}deg(v) \leq 3n$$

Que la suma de grados sea mayor que $3n$ . Si es así, hay un vértice en un camino que tiene un grado mayor que $ \frac {3n}{p}$ donde $p$ es del tamaño de un camino. Y sabemos que un vértice de un camino no puede tener más de $2$ vecinos en un camino, por lo que su grado es menor o igual $n-p+2$ . Desafortunadamente esos dos no se contradicen.

Creo que al menos dos vértices no adyacentes (con $dist(x,y)>2$ ) en un camino debe tener un vecino común fuera del camino. Esto sería una contradicción con el camino más corto. Pero no sé cómo demostrarlo.

Answer 1

Pista: Considere un vértice $v \not\in P$ a lo sumo, ¿cuántos vértices en $P$ que son adyacentes a $v$ ? A partir de eso, en $ \sum_ {u \in P} \deg u$ a lo sumo, ¿cuántas veces un vértice $v \not\in P$ (o $v \in P$ ) se cuenta?

Answer 2

Pista. Deje que $v_0,v_1,v_2, \dots ,v_n$ ser un camino de longitud mínima desde $v_0$ a $v_n.$ ¿Puedes mostrar que $ \deg v_0+ \deg v_3+ \deg v_6+ \cdots + \deg v_{ \lfloor n/3 \rfloor } \le n?$