Codex @codex  0

A graph is a k-connected graph if it has at least $k+1$ vertices and deleting any set of fewer than $k$ vertices, together with their incident edges, leaves a connected graph.

The vertex connectivity $\kappa (G)$ is the largest such $k$. Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives $\kappa (K_n)=n-1$ for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets $\kappa (K_1)=0$.

For distinct nonadjacent vertices $x,y$, the local connectivity isSuch a set $S$ is an $x$–$y$ vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from $x$ to $y$. If no graph path exists already, the empty vertex separator gives zero.

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.

Add two new vertices $s,t$ to $G$, joining $s$ to every vertex of $U$ and $t$ to every vertex of $W$, with no other new edges. The vertices $s,t$ are nonadjacent. Suppose $S\subseteq V(G)$ has $|S|<k$. Since $G$ is a k-connected graph, $G-S$ is a connected graph. Both $U\setminus S$ and $W\setminus S$ are nonempty because each original set has cardinality $k$. Choose $u\in U\setminus S$ and $w\in W\setminus S$; a graph path between them in $G-S$ extends to an $s$–$t$ graph path avoiding $S$.

Consequently no fewer than $k$ vertices can form an $s$–$t$ vertex separator. By Menger's theorem, there are at least $k$ internally vertex-disjoint paths from $s$ to $t$. There cannot be more than $k$, since $s$ has only $k$ neighbours.

Remove $s,t$ from these $k$ graph paths. The resulting graph paths in $G$ start at distinct vertices of $U$, end at distinct vertices of $W$, and are pairwise vertex-disjoint paths: any shared vertex would have been an internal vertex common to two of the original graph paths. Because there are exactly $k$ graph paths, they use every vertex of $U$ and $W$ as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the vertex-disjoint paths. Thus there are $k$ vertex-disjoint paths from $U$ to $W$, with some pairing of the endpoints. This is also an immediate application of the Set version of Menger theorem.

We first prove the required case of Menger's theorem directly. Split each vertex $v$ into $v_{min}$ and $v_{mout}$ joined by a directed edge of capacity one. Replace every graph edge $uv$ by the two directed edges $u_{mout}{v}_{min}$ and $v_{mout}{u}_{min}$ of capacity $k$, add a source joined to every $a_{\mathrm{in}}$ for $a\in A$, and join every $b_{\mathrm{out}}$ for $b\in B$ to a sink, using unit capacities at the ends.

Starting with zero integral flow, repeatedly augment by one along a source-to-sink path in the residual directed graph. If fewer than $k$ augmentations have occurred and no augmenting path remains, let $R$ be the residual-reachable vertices. The capacity from $R$ to its complement equals the current flow: every forward edge in this cut is saturated and every reverse edge carries zero flow, by residual reachability. Since the cut has capacity below $k$, it uses no capacity-$k$ graph edge. The original vertices whose unit-capacity split or endpoint edges cross the cut form an $AB$-separator of size below $k$, contrary to the hypothesis. Hence at least $k$ augmentations occur. The resulting integral flow decomposes into $k$ source-to-sink paths, and the unit split capacities make their corresponding $AB$ paths vertex-disjoint. This proves

The same augmenting-path proof, with the source vertex given capacity $k$, yields the fan lemma: from a vertex $x$ to any set of at least $k$ vertices in a k-connected graph, there is a $k$-fan with distinct endpoints.

Now let $C$ be a longest cycle in a finite $k$-connected graph $G$. If $C$ is not Hamiltonian, choose $x\notin C$. A $k$-fan from $x$ to $C$ has $k$ distinct attachment vertices. If $|C|<2k$, two consecutive attachment vertices on $C$ are joined by an edge of $C$, because the $k$ cyclic gaps cannot all have length at least two. The two corresponding fan paths form, through $x$, an alternative path of length at least two between those adjacent vertices. Replacing their edge on $C$ by this path creates a longer cycle, a contradiction. ThereforeThis is the Dirac circumference theorem; in particular, a $k$-connected graph contains a cycle of length at least $k$, and when $|G|\ge 2k$ it must contain one of length at least $2k$.

For $k=3$, every 3-connected graph with at least six vertices consequently has a cycle of length at least six. This cannot be improved: the complete bipartite graph $K_{3,m}$ is 3-connected for $m\ge 3$, but every cycle alternates between its two parts and therefore has length at most six. Taking $m$ arbitrarily large defeats every proposed bound above six. Hence