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.

$\endgroup$
1
  • $\begingroup$ It seems to be the same thing when I try to use that approach in my code. $\endgroup$
    – utdiscant
    Jan 18 '11 at 15:16
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$.

$\endgroup$

Your Answer

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

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