Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$

Question

Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$

(Chapter 3 Exercise 16.a Chromatic Graph Theory,Gary Chartrand, Ping Zhang)

Attempt: First I observed that the hypotheses of the dirac theorem are fulfilled.

A simple graph with $n$ vertices ( $n\geq 3$) is Hamiltonian if every vertex has degree $\frac {n}{2}$ or greater.

So the graph $G$ is hamiltonian.

And by definition a hamiltonian graph is a graph that contains a hamiltonian cycle (a cycle in G that contains every vertex of G).

So now I have a cycle but I don't know how to get what I need.

Answer 1

There is infact a simpler way to show this directly.

Let $C$ be the Hamiltonian cycle promised, and write the vertex-set of $G$ as $\{v_0,\ldots, v_{100}\}$ such that $v_i$ is adjacent to precisely $v_{i-1}$ and $v_{i+1}$ in $C$, for each $i=0,\ldots, 100$, addition here done $\pmod{101}$ that is. We now show the following:

Claim 1: Label the vertices of $C$ as above, but arbitrarily pick any vertex in $C$ to be $v_0$. Then there is a cycle in $G$ of the form $v_0v_jv_{j+1} \ldots v_{j+25}v_0$, where $v_j\ldots v_{25}$ is a segment of $C$, and where [and this is crucial] none of $v_{j},v_{j+1},\ldots, v_{j+25}$ is $v_0$. Put another way, for any vertex $v_0\in G$, there is a cycle $C'$ in $G$ with precisely $27$ vertices such that at most $2$ edges of $C'$ are not in $C$, and these at most $2$ edges of $C'\setminus C$ are incident to $v_0$.

To this end, let us partition the vertices of $G \setminus \{v_0\}$ into $25$ sets $V_0,V_1,\ldots, V_{24}$ as follows: first $$V_0=\{v_{25},v_{50},v_{75},v_{100}\};$$ then $$V_1=\{v_1,v_{26},v_{51},v_{76}\};$$ and then for each $j=2,\ldots,24$: $$V_j=\{v_j,v_{25+j},v_{50+j},v_{75+j}\}.$$ Then note that there is a cycle $C'$ as claimed if there is an integer $j \in \{0,1,\ldots,24\}$ such that $v_0$ is adjacent in $G$ to at least $3$ vertices in $V_j$. However, there must be indeed be a $j$ such that $v_0$ is adjacent in $G$ to at least $3$ vertices in $V_j$, otherwise $v_0$ could be adjacent in $G$ to at most $2 \times |\{0,\ldots, 24\}|=50$ vertices. So there indeed exists such a $C'$, and so Claim 1 follows.

Now Claim 1 clearly implies the desired result, as any vertex in $G$ can be $v_0$.

---

We note that this method does not generalize to finding cycles of arbitrary odd length between $3$ and $101$. For example, let us suppose $G$ is such that $v_i$ and $v_j$ are adjacent iff the distance between $i$ and $j$ in $C$ is no more than $26$. Then there is no cycle in $G$ of length exactly say $33$ that has at most $2$ edges not in $C$, and the [one or two] edges not in $C$ are incident to a single vertex.