Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 vertice and the properties described as the following:

For example, for k=4, the graph looks like this. There are three vertice on each circle, which connects the vertice 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 vertice. 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>=3. If we think about k as an arbitrary number, my generalized graph has 2(k-1) vertice, 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|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 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. –  Aran Komatsuzaki Oct 1 '13 at 0:15

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.