# 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

1. Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005