Edge versus vertex connectivity

Task number: 3961

Show that each vertex 2-connected graph is edge 2-connected.

(An edge 2-connected graph is such that after removing any edge remains connected.)

  • Solution

    If the graph has a bridge and it is not \( K_2 \), then at least one of the ends of this bridge is adjacent to some other vertex and forms the articulation itself.

  • Variant

    Find the smallest graph that is edge 2-connected but not vertex 2-connected.

  • Variant

    For any pair of integers \( k \geq l \geq 2 \) construct a graph of edge connectivity \(k\) and vertex connectivity \(l\).

Difficulty level: Moderate task
Reasoning task
Solution require uncommon idea
Cs translation
Send comment on task by email