Sheet 2, no. 4:
Let G be a connected graph with n >= 3 (n is the number of vertices of G).
Show that if G has a cutedge, then it has a cutvertex.
Let xy be a cutedge. So G – xy has 2 components (see qn. 6 for the proof that there are exactly 2 components).
Let A be the component that contains vertex x, and B the component that contains vertex y.
Since G (and thus, G-xy) has at least 3 vertices, A and B cannot both contain just one vertex. Without loss of enerality, A must contain at least 2 vertices, i.e. x nd at least one other vertex v.
Now note that removing the vertex x also removes the edge xy, so in G-x, the vertices v and y must be in different components. Thus G-x is disconnected, that is, x is a cut-vertex.
Show by an example that the converse is false.
For the converse, consider two triangles with a common vertex v (i.e. the graph has vertices a,b,v,x,y and edges ab,bv,va and xy,yv,vx).
Then v is a cut-vertex, but there is no cutedge (i.e. removing any edge leaves a connected graph).
