Short Proofs of Some Fan-Type Results

Abstract

For a graph $G$, define $\varphi (G)=min\{max\{d(u),d(v)\}|d(u,v)=2\}$ if $G$ contains two vertices at distance 2, and $\varphi (G)=\mathrm{\infty }$ otherwise. Fan proved that every 2-connected graph on $n$ vertices with $\varphi (G)>\frac{1}{2}n$ is hamiltonian. Short proofs of this result and a number of analogues, some known, some new, are presented. Also, it is shown that if $G$ is 2-connected, $\varphi (G)\ge \frac{1}{2}(n-i)$ and $G–\{v\in V(G)|d(v)\ge \frac{1}{2}(n-i)\}$ has at least three components with more than $i$ vertices, then $G$ is hamiltonian ($i\ge 1$).