Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

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?

share|cite|improve this question
+1 for pretty picture. Did you generate the original? – Rick Decker Sep 30 '13 at 23:42
Thanks, I drew it using 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.