1
$\begingroup$

Question: Let $G$ be a $k$-vertex-connected graph with $k\geq2$. Let $S$ be a set of two edges and $W$ a set of $k-2$ vertices. Prove that there exists a cycle in $G$ containing elements of $S$ and $W$.

My setup: Label the edges of interest: $S=\{e_1,e_2\}$. I know that in a $k$-connected graph, any set of $k$ vertices must be contained in a common cycle, so we can construct a cycle $C$ using the $k-2$ vertices of $W$ and the last 2 (guaranteed) vertices I can choose to be an endpoint of $e_1$ and an endpoint of $e_2$. We label the vertices of $C=\{v_1,v_2,...,v_\ell\}$ in "cycle order" ($v_i$ is adjacent to $v_{i+1}$ in $C$), where $\ell\geq k$.

What I want to do is guarantee that we can include the other endpoint of $e_1$ and the other one of $e_2$ if they're not already included, maybe by using the Fan Lemma to guarantee that the path to that endpoint is disjoint from the rest of $C$ (but I need it to be disjoint from more than $k$ points so I'm not sure if this would work). I also think I'd have to introduce a bunch of different cases: the other endpoint of $e_1$ is already in $C$ and/or the other endopint of $e_2$ is already in $C$. Not only that, but I'm not sure how to guarantee that even if the endpoints are already in $C$, that we can "rearrange" the cycle so that those endopints are adjacent (in $C$) via $e_1$ or $e_2$. It does seem a little unreasonable to introduce all of these cases so I'm looking for a more concise way to approach the problem.

$\endgroup$
1
$\begingroup$

The argument is essentially the same as for the proof that Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

First argue that there's a cycle containing $e_1$ and $e_2$. (Hint: if you add a vertex $v_1$ adjacent to both endpoints of $e_1$ and a vertex $v_2$ adjacent to both endpoints of $e_2$, the resulting graph is still $2$-connected.) Then follow the argument in the answers to the linked question to insert the vertices in $W$, one at a time.

$\endgroup$
3
  • $\begingroup$ Thanks for the hint, I was able to easily show that $e_1$ and $e_2$ are in a common cycle. However, what I am confused by is being able to add all $k-2$ vertices of $W$. If we start the cycle with the at least $3$ vertices of C, how can we be guaranteed to be able to construct a cycle containing at least $k+1$ vertices (e.g. how can I be sure I can add the last vertex, or 2 vertices if $e_1$ and $e_2$ don't share an endpoint) to the cycle? $\endgroup$
    – ninja cat
    Mar 29 '20 at 4:55
  • $\begingroup$ Have you read the answers to the linked question? The argument is exactly the same. $\endgroup$ Mar 29 '20 at 5:00
  • $\begingroup$ I had read it, but my confusion was based on a misunderstanding of the proof. Upon thinking about the problem for a little while longer and rereading the proof as suggested, I managed to see that my initial notion was incorrect. $\endgroup$
    – ninja cat
    Mar 29 '20 at 9:27

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.