1
$\begingroup$

I need to Show that Every edge of a 2- Connected graph is either contractible or Deletable.

Contractible Edge:- To contract an Edge, remove it and its end points(vertices) should be merged along with other edges incident on them.

Deletable Edges:- A edge e is Deletable from Graph G if we remove that edge from Graph it don't change the Connectivity(Kappa) of that graph. i.e. Kappa(G)=Kappa(G-e)

An Example of Deletable and Contractible Edges can be found in Bondy and Murty.

I am starting as this..

Since given that the graph is two connected, there exists atleast two distinct internally disjoint paths between any pair of vertices. There fore Kappa Prime which is edge connectivity is greater than or equal to 2 . Thus G don't have cut edges.

So, an edge can be a loop or a Parallel Edge or a normal edge. I am able to see that a loop is either contractible or deletable.

So, I am not sure on how to proceed from here. Can someone kindly guide me.

Thanks,

$\endgroup$
  • $\begingroup$ So an edge $e$ is contractible if Kappa($G$)=Kappa($G-e$), right? $\endgroup$ – D. N. Mar 24 '14 at 4:35
  • $\begingroup$ Yes.. BTW can you also let me know how to contract a Parallel Edge? I presume that it should result in a self loop. Is that right? $\endgroup$ – Pavan K Mar 24 '14 at 5:27
  • $\begingroup$ I think your result is not correct. If you take the graph $G$, with vertex set $\{x_i,y_i,x,y\mid 1\leq i, j \leq 6\}$, and edge set $\{\{x_i,x_j,\},\{y_i,y_j\},\{x,x_i\},\{y,x_i\},\{x,y_i\},\{y,y_i\},\{x,y\} \mid i\in \{1,\dots,6\}\}$, then if you contract the edge $x--y$, the new graph will be 1-connected. $\endgroup$ – D. N. Mar 24 '14 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.