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$