1
$\begingroup$

Let $G$ be a connected simple graph $G=(V,E)$ with $n=|V|>2$. I am trying to prove that, if every vertex in $G$ has degree at least two then it has a cycle (a sequence of vertices $v_1,v_2, ..., v_m$ such that $(v_i,v_{i+1}) \in E$ for each $0\leq i < m$ and $(v_m,v_1)\in E$) such that the number of vertices in the cycle connected to strictly more than 2 other vertices is no more than $2\lceil \lg n \rceil + 1$.

Not being sure where to begin I started with induction, where $n=3$ is easy. If we assume this is true for all graphs up to $n$ then we consider $G=(V,E)$ with $|V|=n+1$. Let $v\in V$ and let $A$ be the set of vertices adjacent to $v$. We want to somehow reduce this to this to a smaller problem so that we may leverage the inductive hypothesis. Typically we remove a vertex and consider the subgraph, but in this case if we do so, the subgraph may lose the property that every vertex is connected to at least two vertices. We may put extra connections into $A$ in order to remedy this, but I've found that I don't know how to move from that back to the super-graph $G$.

Wondering if that was a mis-step, I started thinking about $A$ and the fact that it can determine a subgraph of size smaller than $n+1$, but again this requires disconnecting some edges and so implies a challenge with satisfying the conditions of the inductive hypothesis.

From here I'm thinking that I could do an inductive proof inside of an inductive proof--this time on the number of edges. But this sounds like grabbing at straws and I don't foresee how this will shake out. Perhaps induction is the wrong approach. We know that every graph of degree at least two has a cycle. I could try proving that this cycle must have at most the desired number of vertices with degree greater than 2, but that would be false: In the case of a complete graph of adequate size, we could pick the cycle that tours the whole graph. That cycle will not have the necessary property. In the case of a complete graph we want to pick the smallest possible cycle which would be a 3-cycle, in which case because the size of the cycle is itself smaller than bound and therefore satisfies it trivially.

I'm trying to see if this observation is any kind of insight into the proof. Maybe we assume that there is a cycle with more than $2\lceil \lg n\rceil +1 $ vertices (if it doesn't then there's a smaller cycle and the theorem is satisfied trivially). Then maybe assume this graph has more than the desired number of vertices of degree greater than 2, and perhaps look at its complement? But this seems to be another dead-end because I don't see why its complement must be a cycle, or must have a cycle of any particular size, or that the cycle must have so-many vertices of degree 2.

$\endgroup$
1
$\begingroup$

Well, to begin with, we may reduce this question to one about graphs with minimum degree $3$.

Suppose that a vertex in $G$ has degree only $2$. Then we may "smooth out" that vertex: delete it from the graph, replacing it by an edge joining its two neighbors. If we prove that the new graph $G'$ has a cycle with at most $2\lg (n-1)+1$ vertices of degree $\ge 3$, then the original graph $G$ had a cycle with at most $2\lg (n-1)+1$ (and therefore at most $2 \lg n+1$) such vertices. After all, even if the cycle used the edge where the deleted vertex used to be, adding the vertex back in by subdividing that edge won't change tha number of vertices of degree $\ge 3$ on the cycle.

This smoothing process can be done any number of times. We might eventually get a $K_3$ as a connected component (in which smoothing out any vertex leaves a multigraph, which is a problem, but which also contains a cycle with no vertices of degree $\ge 3$). Otherwise, we'll be left with a graph that has no vertices of degree $2$ to smooth out.


In such a graph, from any vertex $v$ there are at least $3 \cdot 2^{k-1} > 2^k$ paths of length $k$ starting at $v$. (Or at least there are that many non-backtracking walks, which go to a vertex and then keep going to a vertex that's not the one they arrived from. But if they repeat a vertex, then we immediately get a cycle shorter than $k$ and we're done, so we assume they are paths.) Take $k = \lceil \lg n \rceil$; then there are more than $n$ such paths, so by the pigeonhole principle two of them must share an endpoint. This gives us a path with at most $2k+1$ vertices.

$\endgroup$
2
  • 1
    $\begingroup$ So I mostly get this, but how do we know that, in the multi-graph, some of the paths that we count with $3\cdot 2^{k-1}$ don't, along the way, connect to a vertex already visited and therefore possibly only have one remaining choice of edge? $\endgroup$
    – Addem
    Mar 21 '18 at 4:05
  • $\begingroup$ Good question! I was a bit sloppy with that case. But if anything like that happens, we actually get a cycle shorter than length $k$, which is also good enough for us. I've edited my answer to include this. $\endgroup$ Mar 21 '18 at 4:34

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.