2
$\begingroup$

Consider the following graph:

enter image description here

  1. The edge connectivity should be $2$. We can think this in two way:

    • If I cut edge $(1,2)$ and $(2,4)$, the node $2$ is disconnected from the whole graph.
    • Also, edge connectivity can be thought as the network flow problem, the maximum number of edge-disjoint paths from node $1$ to node $2$ is $2$.
  2. According to the property that vertex connectivity $\leq$ edge connectivity, the answer for vertex connectivity should be less or equal $2$.

However, I delete node $4$ and node $6$ and all edges connecting both; the graph is still connected. Both nodes are the nodes with maximal degree.

Where am I wrong?

Note: the degree of node $5$ and node $7$ are $4$

$\endgroup$
  • $\begingroup$ We have vertex conn. $\leq$ edge conn. because for any edge-set $E'$ that disconnects the graph, one can find a vertex-set of the same size that disconnects the graph: just pick one endpoint of every edge of $E'$. Can you use that? $\endgroup$ – Manuel Lafond Apr 16 '16 at 3:26
  • 1
    $\begingroup$ @ManuelLafond You mean pick node $1$ and node $9$. So the vertex connectivity is also $2$? $\endgroup$ – sleeve chen Apr 16 '16 at 3:31
2
$\begingroup$

Let $G$ be a graph and let $\kappa(G)$ be the size of any minimum vertex separating set of $G$, $\lambda(G)$ be the minimum size of any edge separating set of $G$, and let $\delta(G)$ be the minimum degree of $G$. It is well known that $$\kappa(G)\le\lambda(G)\le\delta(G).$$ Since $\delta(G)=2$ and $G$ is connected then $\kappa(G)=1\text{ or }2$. Can you show that $\kappa(G)\ne 1$?

When you are drawing graphs, edges should never meet unless they are crossing or share a vertex in common and they should only meet in those locations. The way you have drawn your graph seems to indicate that $\deg(v_5)=3$ when it is really true that $\deg(v_5)=4$. Similarly for $v_7$.

$\endgroup$
  • $\begingroup$ I just know that $0 < \lambda_2(G) \leq \lambda (G)$ where $\lambda_2(G)$ is the second minimal eigenvalue of laplacian matrix $\endgroup$ – sleeve chen Apr 16 '16 at 3:43
  • $\begingroup$ Yes, deg($v_5$) $=4$, similar for $7$. Sorry for bad drawing $\endgroup$ – sleeve chen Apr 16 '16 at 3:45
  • $\begingroup$ I guess what I was trying to say in my hint at the end of the first paragraph is that we know that $\kappa(G)\le2$. In order to claim that $\kappa(G)=2$, then we have to show that $\kappa(G)\ne1$. In this particular instance, you could claim that the deletion of any one vertex does not disconnect the graph by inspection and conclude that $\kappa(G)=2$. Then $\lambda(G)=2$ by Squeeze Theorem. $\endgroup$ – Laars Helenius Apr 16 '16 at 4:06
2
$\begingroup$

Vertex connectivity describes the minimum number of vertices you can remove to disconnect the graph. Not every pair needs to disconnect it in this case.

$\endgroup$
1
$\begingroup$

If you remove vertices 1,9 and all the edges that falls on those vertices, then the vertex 11 tends to separate from the graph and hence result into disconnected graph. So this gives edge connectivity = 2 and vertex connectivity = 2 as well.

Hence vertex connectivity <= edge connectivity.

$\endgroup$

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.