Proof
(related to Proposition: Characterization of Cutvertices)
"\(\Rightarrow\)"
- Let \(v\) be a cutvertex in the connected graph \(G(V,E,\gamma)\).
- Since the subgraph \(G[V\setminus v]\) is disconnected, it is not empty and has at least two vertices \(x,y\in V\), which are in different components of this graph left after the removal of the cutvertex \(v\).
- Moreover, every path between \(x\) and \(y\) must pass \(v\).
- For if a path between \(x\) and \(y\) existed, which does not pass \(v\), the removal of the vertex \(v\) would not leave the graph \(G\) disconnected, in contradiction to \(v\) being a cutvertex.
"\(\Leftarrow\)"
- Let \(x,y,v\) be different vertices of \(G\) such that every path between \(x\) and \(y\) passes \(v\).
- Then the removal of \(v\) cuts all these passes and there is no path between \(x\) and \(y\) in the graph \(G[V\setminus v]\).
- Thus, \(G[V\setminus v]\) is disconnected and \(v\) is a cutvertex.
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005