Prove that a graph with a cycle for every $n+1$ vertices is $n$-connected.

Question

Let $G$ a graph with at least $n+1$ vertices. Suppose that for every $n+1$ vertices $(v_1,\ldots,v_{n+1})$ exists a cycle which traverses the vertices in the given order. Prove that $G$ is $n$-connected.

I tried to prove this by contradiction I supposed that exists a set $X\subset V$ of vertices with $|X|\leq n-1$, we can say $X=\{v_1,\ldots v_{n-1}\}$ such that $G\setminus X$ is disconnected. I think that here I can use that exists at least two components and choose $u,v$ two vertices for each component. Then for hypothesis exists a cycle in $G$ that traverses the vertices $(u,v_1,\ldots,v_{n-1},v)$ in the given order. But I can not see how to continue and conclude it. I do not know if I chose the right path, any help or hint will be helpful.

Answer 1

Consider the cycle containing $u, v_1, \ldots, v_{n - 1}, v$ in this order. Let the cycle be $(u, v_1, \ldots, v_{n - 1}, v, x_1, \ldots, x_{m}, u)$., then even after removing $X$, there still remains a path between $u$ and $v$, namely, $(v, x_1, \ldots, x_m, u)$, contradicting the assumption that $u$ and $v$ belong to different components.

Answer 2

To prove that a graph with a cycle for every n+1 vertices is n-connected, we will show that any two distinct vertices in the graph have at least n vertex-disjoint paths between them.

Consider any two distinct vertices v1 and v2 in the graph. By the assumption that there is a cycle for every n+1 vertices, there is a cycle that contains both v1 and v2. This cycle forms a path between v1 and v2. Now, we can remove one vertex from the cycle and still there is a cycle for every n vertices. We can repeat this process and remove one vertex in each step until we have n cycles containing vertex v1 and v2.

Therefore, we have shown that there are n vertex-disjoint paths between any two distinct vertices in the graph. So, the graph is n-connected.

It's important to note that the above reasoning is based on the assumption that the cycles are vertex disjoint, if the cycles share vertices, it is not guarantee that we can remove n vertices to get n vertex disjoint cycles containing both v1 and v2.