There is a graph G with a variable k. The following is the graph G when k=3. There are three vertice on each green circle line, and each of (1,2,3) is assigned to each of the green line.The graph has a property such that if the edge labeled with i is cut, another edge labeled with i is also cut. When k is an arbitrary number, in the graph G there are k vertice on each green circle line, and each of (1,2,...k) is assigned to each of the green line. Each point on the upper circle is edge-connected by red edges with every points on the lower circle like the graph G when k=3.
Is this graph (k+1)-edge-connected?

enter image description here

  • 2
    $\begingroup$ Perhaps I'm misunderstanding the problem, but your graph is just $K_{k,k}$ (the complete bipartite graph) with the vertices circularly joined. Even if the green edges were not present, the graph will still be $k$-connected since $K_{k,k}$ is $k$-connected. I'm not sure what you mean by "the graph has a property such that if the edge labeled with $i$ is cut, another edge labeled with $i$ is also cut" or how it plays into the question. $\endgroup$ – EuYu Oct 1 '13 at 6:17
  • $\begingroup$ Yes. This graph is exactly the same as K_k,k with the vertices circularly joined. Thanks for simplifying my explanation. I'm sorry, but I realized that there is an error in my question. "k-connectivity" should be changed as "(k+1)-connectivity. So, I cannot delete all edges of the cycle. k-connectivity means that, as you know, no matter how the graph is cut k times, the graph is connected. $\endgroup$ – Math.StackExchange Oct 2 '13 at 1:59
  • $\begingroup$ For my graph, for example, if the edge labeled with "1" which is on the upper circle is cut, simultaneously the edge labeled with "1" which is on the lower circle must be cut. These two cuts are counted as ONE cut because of the synchronizing property of the green edges. $\endgroup$ – Math.StackExchange Oct 2 '13 at 2:00
  • $\begingroup$ By $k$-connectivity, you mean edge connectivity right? The term connectivity is typically reserved for vertex connectivity. $\endgroup$ – EuYu Oct 2 '13 at 2:54
  • $\begingroup$ Yes. I meant edge connectivity. I just changed my error in the above question, so it shows (k+1)- edge connectivity instead of k-connectivity. $\endgroup$ – Math.StackExchange Oct 2 '13 at 5:51

We need to show that $k$ edges are insufficient to disconnect the graph.

Suppose for the sake of contradiction that some $k$ edges disconnected the graph. Since all the vertices are part of the $K_{k,k}$ subgraph, it is necessary to disconnect $K_{k,k}$. But $K_{k,k}$ has edge connectivity $k$ and so it follows that all $k$ edges used to disconnect the graph are used on the $K_{k,k}$ subgraph. But this means that the green edges are untouched and since there exists at least one edge remaining in $K_{k,k}$ which joins the $2$ green circles, it follows that the graph is connected. This is contrary to the assumption that the $k$ edges disconnects the graph. Therefore the graph has edge connectivity at least $k+1$.

In fact, we can easily extend the above argument to show that the graph is in fact $k+2$ connected. This is the best possible since your graph is $(k+2)$-regular.

  • $\begingroup$ I appreciate you for developing the solution to the case of (k+2)-edge-connectivity. Though I initially intended to prove this problem in order to solve another more complicated problem, this unexpected progress gave me chance to widen the extent of my investigation. I think your reasoning which had been used until you got the conclusion about (k+1)-edge-connectivity is kind of similar to mine shown in the second post, yet yours is simpler and sophisticated. $\endgroup$ – Math.StackExchange Oct 2 '13 at 6:20

Since I got an idea which seemed workable, I will show it in the following. enter image description here

Let's call my graph which consists of two green circular edges and K_(k,k) as G. I check (k+1)-connectivity of G. In the above, flattened graph, green edges represent the circular green edges drawn in the first graph, and red edges and the area inside the rectangle represent the red edges drawn in the first graph. If I first cut the upper edge labeled with "n," simultaneously the lower edge labeled with"n" is cut. (These cuts are counted as one cut.) Thus, I get an rectangle which consists of K_(k,k) and the rest of the green edges. No matter how I cut the red edges k times, K_(k,k) is connected. Therefore, if there exists the way to disconnect G by cutting edges (k+1) times, it is the way such that no green edge is cut. However, to disconnect G without cutting green edges, I need to cut all red edges. Hence G has (k+1)-connectivity.

  • $\begingroup$ I think you're almost there. But it is possible to disconnect $K_{k,k}$ with $k$ edge cuts: cut off all the edges of any single vertex for example. $\endgroup$ – EuYu Oct 2 '13 at 2:58
  • $\begingroup$ In that case, there are also green edges connecting each vertices, so this graph is not simply K_(k,k) but combination of K_(k,k) and all the green edges except for the ones labeled with "n." $\endgroup$ – Math.StackExchange Oct 2 '13 at 5:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.