Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show that there is a path of length $k$ in $G$.

My first thought was that if $G$ is Hamiltonian it would contain a cycle of length $n$ which contains a path of length $k$, since $ k \leq n$.

Suppose $G$ is not Hamiltonian, so there is non cycle of length $n$ in $G$.

Let $P = v_0v_1 \dots v_{l}$ be an open path of maximum length $l$ in $G$. Suppose there is a cycle $C$ of length $r$ in $G$. Then $r <n$, so there is a vertex $w$ that does not lie on $C$. As $G$ is connected, there is a path form $w$ to $C$ which, together with $r-1$ edges of $C$, gives an open path of lengthe$\geq r$. Hence $r \leq l$.

See the end of the solution below.

  • $\begingroup$ Consider the lane : 1-2-3-4, there is no edge between 1 and 4, so the $k$ no more than 2. But there is no path with length 2. $\endgroup$ – openspace Jan 23 '16 at 16:56

Continuing the above line of thought:

Let $A=\{v_i \in V(P) : v_0v_{i+1} \in E(P)\}$ and $B=\{v_i \in V(P) : v_0v_{l} \in E(P)\}$. If $v_i \in A \cap B$ then $v_0 \dots v_iv_l \dots v_{i+1}v_0$ is a cycle of length $l+1$. Hence A and B are disjoint, so $|A|+|B|\leq |V(P)| = l+1$.

$v_0$ is not adjacent to $v_l$. All vertices adjacent to $v_0$ or $v_l$ are in $V(P)$, otherwise $P$ could be extended. Thus $|A| = d(v_0)$ and $|B| = d(v_l)$.

Hence $l +1 \geq d(v_0 +d(v_l) \geq k$, so $P$ contains a path of length k.


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.