9
$\begingroup$

Problem

Find the cut vertices and cut edges for the following graphs

cuts

My understanding of the definitions:

A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph.

A cut edge is an edge that when removed (the vertices stay in place) from a graph creates more components than previously in the graph.

My Answers

31) The cut vertex is $c$. There are no cut edges.

32) The cut vertices are $c$ and $d$. The cut edge is $(c,d)$

33) The cut vertices are $b, c, d$ and $i$. The cut edges are: $(a,b)$,$(b,c)$,$(c,d)$,$(c,e)$,$(e,i)$,$(i,h)$

For anyone reading this at a later date:

33) is wrong, per the answers and comments below, e is a cut vertex, not d

$\endgroup$
4
$\begingroup$

You're correct except that in $33$, $d$ is not a cutvertex and $e$ is.

$\endgroup$
3
$\begingroup$

Good job except on 33) $d$ is not a cut vertix and $e$ is . and the cut edges are $(b,c) ,(c,e) ,(e,i)$ 32) and 31) seems correct for me .

$\endgroup$
  • 1
    $\begingroup$ I believe the cut edges for 33) are still $(a,b),(b,c),(c,d),(c,e),(e,i),(i,h)$. For example, when edge $(a,b)$ is removed, vertex $a$ still exists as a separate component. $\endgroup$ – user87509 Aug 1 '13 at 11:05
  • $\begingroup$ you are right i am sorry for misleading you. $\endgroup$ – Eli Elizirov Aug 1 '13 at 11:06
  • $\begingroup$ No, I appreciate your help. Thank you. $\endgroup$ – user87509 Aug 1 '13 at 11:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.