a 2-connected graph has an extra vertex
Source: 239 2000 S4
May 18, 2020
graphgraph theoryConnected graphsConnectivitycombinatorics
Problem Statement
A graph is called 2-connected if after removing any vertex the remaining graph is still connected. Prove that for any 2-connected graph with degrees more than two, one can remove a vertex so that the remaining graph is still 2-connected.