2
$\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 Answer 1

2
$\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, 2020 at 4:55
  • $\begingroup$ Have you read the answers to the linked question? The argument is exactly the same. $\endgroup$ Mar 29, 2020 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, 2020 at 9:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .