0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ A cut vertex makes the graph disconnect after being removed. Your drawing doesn't prove that. You need to use words to explain why removing $c$ disconnects $G$. Also, notice the "if and only if" statement ? This means you need to do two proofs. First, that if $c$ is a cut vertex, then there are vertices $u$ and $v$ as described. And second, the other direction - if such $u$, $v$ exist, then $c$ is a cut vertex. $\endgroup$ Mar 3, 2015 at 20:33
  • $\begingroup$ ok and how would i prove those two cases? $\endgroup$ Mar 3, 2015 at 21:01

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .