[Graph theory] k-vertex-connectivity implies k-edge-connectivity... does it?
Hey all!
It makes perfect sense: if a graph is k-vertex-connected, for every vertex removed I'm removing at least 2 edges, so why wouldn't it be k-edge-connected?
However, what if my graph has 2 vertices and a lonely edge connecting them. The graph would be 2-vertex-connected (I'm assuming the remaining vertex makes a trivially connected graph) but removing the edge would disconnect the graph!
Does the rule only hold when both vertices and edges are greater or equal than k? It would be pretty silly otherwise... right?
Posted Sep 30, 2017, 8:15 AM UTC
24
Your intuition is correct that, in general, if a graph is k-vertex-connected, then it is also k-edge-connected. We just need to be careful with definitions to ensure that your example isn't a special case.
By definition, for a graph to be k-vertex-connected, it must (1) have more than k vertices and (2) remain connected if any fewer than k vertices are removed. Thus, the path with 2 vertices is 1-connected, and more generally, any complete graph with n vertices is n-1-connected.
Thank you! so the case I mentioned would be a special case in a theorem about vertex-connection implying edge-connection? e.g. k-vertex-connectivity implies k-edge-connectivity as long as |V|>=k and |E|>=k?
No; I was perhaps unclear in not explicitly correcting your example. The complete graph with 2 vertices is 1-connected, not 2-connected.
It's maybe easier to see the need for convention in the definitions if we look at connectivity instead of connectedness. That is, we would like to define the vertex-connectivity k(G) of a simple graph G to be the minimum number of vertices whose removal disconnects G (i.e., leaves two connected components). This isn't quite enough, though; what is k(K_n) for a complete graph K_n with n vertices? No matter how many vertices we remove, we never get two separate connected components.
We define k(K_n)=n-1. (Or, if you like, we can extend our definition so that K(G) is the minimum number of vertices whose removal leaves either two components or a single vertex. Either way, k(K_n)=n-1.) In particular, k(K_2)=1.
For edge-connectivity, we would like to define the edge-connectivity k'(G) of a simple graph G to be the minimum number of edges whose removal disconnects G. Although all complete graphs were a "problem" that we had to handle for vertex-connectivity, in this case the only problem situation is G=K_1, where again, we fix the problem by defining k'(K_1)=0.
Given these definitions, we get the following "clean" version of the theorem that is consistent with your original intuition: for any simple graph G, k(G)<=k'(G).
Sorry, I only got a chance to read now. Thank you so much, it's now perfectly clear :)