# Odd problem about graph connectivity

This problem asks how to prove that a graph has $k$-connectivity. However, there's something which makes the problem intricate. The graph which I'm studying about is a graph with $2k-2$ vertices and the properties described as the following:

For example, for $k=4$, the graph looks like this. There are three vertices on each circle, which connects the vertices on it with three green edges. There are also red edges between a vertex in the lower circle and one in the upper circle for every possible combination of such vertices. Thus, $|E|=15$ and $|V|=6$. However, this graph has a property such that if a green edge is cut, the green edge with the same number on the opposite edge also has to be cut. The above graph shows the case of $k=4$. However, I need to prove $k$-connectivity of such a graph for arbitrary $k\geq 3$. If we think about $k$ as an arbitrary number, my generalized graph has $2(k-1)$ vertices, $k-1$ circular green edges for each circle (there are always only two circles,) and $(k-1)^2$ red edges connecting between a vertex in the low and one in the up for every possible combination. A number from $\{1,2,...k-1\}$ is assigned to each green edges in the upper circle, so that every edges have distinct number. For the lower circle, the same assignment is done (from $\{1,2,...k-1\}$.)

How I prove that such graph has $k$-connectivity?

• +1 for pretty picture. Did you generate the original? – Rick Decker Sep 30 '13 at 23:42
• Thanks, I drew it using OpenOffice.org Drawing. This tool is especially useful to draw a graph which has some specific pattern because it has flexible option of duplicating drawn object. It is also easy to draw a curve and some elementary objects used in Geometry. – Math.StackExchange Oct 1 '13 at 0:15