A cycle of size at least $\frac{n}k$ in a graph with at least $3k$ vertices

Question

My question is this: In a $G=(V,E)$ where $\alpha(G)\leq k$ (the maximum of the size of an independent subset of $G$) and $|V|=n\geq3k$, show that there is a cycle of size $\geq \frac{n}k$.

Now, $\chi(G)\geq \frac{n}{\alpha(G)}\geq \frac{n}k\geq3$. Let's examine an optimal vertex-painting of $G$, there are at least $3$ chromatic sets: $C_1, C_2, \dots, C_m$ (where $m$ is the chromatic number of $G$). It can be proven that there is a vertex with at least $2$ neighbors, so let's start the cycle at that vertex and connect it to both of its neighbors. Now let's connect the two neighbors by covering all of the remaining chromatic sets. In the test I had, I made the false assumption that each vertex must be connected to one of the members of a chromatic set to which it doesn't belong. But this is not true, all I can assume is that between two different chromatic sets there must be an edge (otherwise we could take their union as one chromatic set). I need to find a way to get around this difficulty and create a cycle which is based on the $m$ chromatic sets (for $m\geq \frac{n}k$, proving what needs to be proven). If another way altogether is suggested, I'll be much obliged all the same. Thanks.

Answer 1

One has to use the following two basic theorems, which can for instance be found in Reinhard Diestel, Graph Theory (Fourth Edition), Springer Graduate Texts in Mathematics. For a graph $G = (V,E)$ we let $\delta(G)$ denote the minimum degree of $G$:

$$ \delta(G) = \min_{v\in V} d(v). $$

If $H \subseteq G$ is a subgraph and $v\in V$ is a vertex, then we write $d_H(v)$ for the degree of $v$ relative to $H$.

Theorem 1 (Diestel proposition 5.2.2). Every graph $G = (V,E)$ contains a subgraph $H \subseteq G$ with $\delta(H) \geq \chi(G) - 1$.

Proof. First we construct an enumeration of the vertices of $G$ in the following way:

• Let $v_n$ be a vertex of minimum degree in $G$;
• Let $v_{n-1}$ be a vertex of minimum degree in $G \setminus \{v_n\}$;
• $\ldots$
• Let $v_i$ be a vertex of minimum degree in $G \setminus \{v_{i+1}, v_{i+2}, \ldots, v_{n-1}, v_n\}$.

Note: the degree we consider in each step is the degree relative to the remaining subgraph $G \setminus \{v_{i+1},v_{i+2},\ldots,v_{n-1},v_n\}$, not the degree in the original graph $G$.

Now we construct a greedy colouring of $G$ in the reverse direction, from $v_1$ to $v_n$. If vertices $v_1,\ldots,v_{i-1}$ have already been coloured, then we colour $v_i$ with the smallest integer $k\geq 1$ that does not occur among its neighbours on the left. Now let $C$ be the number of colours used in this colouring and let $j \in \{1,\ldots,n\}$ be an index such that $v_j$ receives colour $C$. Now $v_j$ must have at least $C - 1$ neighbours to the left (coloured $1$ through $C - 1$). Since we chose $v_j$ as a minimum degree vertex in $G \setminus \{v_{j+1},v_{j+2},\ldots,v_{n-1},v_n\}$, it follows that $$\delta\big(G \setminus \{v_{j+1},v_{j+2},\ldots,v_{n-1},v_n\}\big) \geq C - 1 \geq \chi(G) - 1.\tag*{$\Box$} $$

Why is this useful? Because graphs of large minimum degree contain large cycles:

Theorem 2 (Diestel proposition 1.3.1). Every graph $G = (V,E)$ satisfying $\delta(G) \geq 2$ has a cycle of length at least $\delta(G) + 1$.

Proof. Let $x_0\cdots x_k$ be a simple path of maximum length. Then all neighbours of $x_k$ lie on this path, for otherwise the path could be extended. (See image below.) As we have $d(x_k) \geq \delta(G) \geq 2$ by assumption, we know that $x_k$ has another neighbour (apart from $x_{k-1}$). Now let $i\in\{0,\ldots,k-2\}$ be the minimum index of a neighbour of $x_k$, then we have a cycle $x_ix_{i+1}\cdots x_{k-1}x_k$ that contains all neighbours of $x_k$ as well as $x_k$ itself. Thus, this cycle has length at least $\delta(G) + 1$. $$\tag*{$\Box$}$$

Putting these results together, we find

Corollary 3. Every graph $G = (V,E)$ satisfying $\chi(G) \geq 3$ has a cycle of length at least $\chi(G)$.

I'm sure you can take it from here. :-)

---

As a side note, the following example shows that $\frac{n}{k}$ is optimal, in the sense that there are graphs satisfying $\alpha(G) \leq k$ and $n \geq 3k$ that have no cycle larger than $\lceil \frac{n}{k} \rceil$. For instance, fix some integer $r\geq 3$ and consider the graph $G$ obtained by taking $k$ disjoint complete graphs $K_r$ and adding a single vertex that is connected to every other vertex. Thus, now we have $k$ cliques of size $r + 1$ that all have exactly one vertex in common. This is illustrated by the example below ($k = 3$ and $r = 9$).

Now the following results hold:

• We have $\alpha(G) = k$, since no independent set can have two or more vertices from the same clique;
• Clearly we have $n = kr + 1 \geq 3k$;
• The largest cycle has length $r + 1$: there is only one vertex that takes us from one clique to another, so we cannot leave whichever clique we start in and later return to it.