-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What is $K_2$?? $\endgroup$
    – Ramanujan
    Dec 20 '19 at 22:30
  • $\begingroup$ The complete graph with 2 vertices. $\endgroup$ Dec 20 '19 at 23:29
  • $\begingroup$ The title mentions edge contraction, so presumably $G/e$ means the graph obtained from $G$ by removing edge $e$ and identifying the two vertices it previously connected. If I understand the meaning of $G/e$ separable, it should be connected but not $2$-connected. Does the statement beginning "Apparently..." ask for confirmation of the claim, or does it serve as additional assumptions? $\endgroup$
    – hardmath
    Dec 21 '19 at 19:55
  • $\begingroup$ That is true - $G/e$ being separable means that it is 1-connected but not 2-connected (that is the definition of seperable). I used the word apprently as I have not seen the proof yet so it is a claim is true (made in a research paper) but for me to say it is true, will have to see how, which is why I am here :) $\endgroup$ Dec 21 '19 at 22:18
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ In particular, this example shows that there do not necessarily exist two 2-connected graphs $G_1$ and $G_2$ as in the question. $\endgroup$ Dec 20 '19 at 18:45
  • $\begingroup$ Actually, I must apologise that there was a lemma that also implied that given some constraints are satisfied, the Graph $G$ is also two-connected. Just made the edit. $\endgroup$ Dec 20 '19 at 20:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.