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?

  • $\begingroup$ +1 for pretty picture. Did you generate the original? $\endgroup$ – Rick Decker Sep 30 '13 at 23:42
  • $\begingroup$ 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. $\endgroup$ – Math.StackExchange Oct 1 '13 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.