Consider the following graph:
-
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$.
-
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$
Best Answer
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$.