1
$\begingroup$

I want to determine if a given graph is a minimal 3-connected graph. That is, deletion of any edge will reduce the vertex connectivity to 2.

My approach right now, is to look at every edge where both endpoints have degree 4 or more, remove the edge and see if the vertex connectivity has decreased to 2 in the whole graph.

My question is, can I use the following approach instead: Look at every edge $e=xy$ where both endpoints have degree $\geq$ 4. Remove $e$ and check if the connectivity between $x$ and $y$ has decreased.

So I want to know if I can reduce the problem to considering only the connectivity between the endpoints of the edge I am removing.

Improve this question
$\endgroup$
1
  • $\begingroup$ It seems to be the same thing when I try to use that approach in my code. $\endgroup$
    – utdiscant
    Commented Jan 18, 2011 at 15:16

1 Answer 1

Reset to default
2
$\begingroup$

I would say yes. If the connectivity between $x$ and $y$ has decreased, then obviously the connectivity of $G$ has decreased. On the other hand, if $G - e$ is not 3-connected, then there are a pair of subgraphs $(A,B)$ such that $G-e=A \cup B$, and $|V(A) \cap V(B)|=2$. Since $G$ is 3-connected, this implies that $e$ must have one endpoint in $V(A)-V(B)$ and the other in $V(B)-V(A)$. Hence the connectivity between $x$ and $y$ has indeed decreased in $G-e$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .