11
$\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$
5
$\begingroup$

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

$\endgroup$
0
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$
3
  • 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$ Aug 1 '13 at 11:06
  • $\begingroup$ No, I appreciate your help. Thank you. $\endgroup$
    – user87509
    Aug 1 '13 at 11:06