so I recently started learning about the graph theory and i came about this question:
Show that a vertex c in the connected simple graph G is a cut vertex
if and only if there are vertices u and v, both different from c, such
that every path between u and v passes through c.
So from what i understand, a cut vertex is an vertex that if removed, would create 2 graphs from the original. Correct? So to prove the question above, would I simple do:
u---c---v
Is this correct? if not how would I show such case?
Best Answer
Well, we have to prove two implications. Suppose that $G$ is simple, undirected graph:
$\Rightarrow:$
Let's say we've got two vertices, $u ,v\neq c$ such that every path between them passes through $c$ . Let's remove $c$ from $G$ - we just cut every single way to get from $u$ to $v$ (and vice versa) so graph isn't connected anymore (look at definition of connectivity - graph is connected if and only if we can find path from any vertex to any other) - $c$ was cut vertex.
$\Leftarrow$ :
Let's say that $c$ is cut vertex. Then, if we remove it from graph, it will constist of at least two connected components ($G$ was connected before, so it was one connected component). Let's take $u$ from one of them, and $v$ from another - if now there's no way between them, when we had $c$ in graph, all paths between them must have contained $c$ - if there would be any that had not, it would still exist, and $u , v$ would not be in other components.