Elementary question on Graph Theory, Edge Contraction and Separability

114 Views Asked by At

Let $G = (V,E)$ be a 2-connected, simple graph. Apparently, if $G/e$ is separable then there exist two 2-connected graphs $G_1$ and $G_2$ such that $G_1 \cup G_2 = G$ and $G_1 \cap G_2 = K_2$. I wonder does the contracted edge in $G$ (and the resulting vertex $G/e$) have to be the vertex of articulation of $G/e$? It's hard to visualise how this works out.

1

There are 1 best solutions below

2
On

There may be other vertices of articulation of the original graph which are not adjacent to the edge you contract. Imagine a square ABCD (4 vertices 4 edges connections in cyclic order) and two extra vertices E and F with D connected to E and E connected to F. This graph G is 1 connected with either D or E being vertices of articulation. If you contract AB i.e. look at G/AB, then it is still one connected but the new vertex AB is not a vertex of articulation.

You may need a hypothesis like G is 2 connected to get such a conclusion. I haven't thought it through though.