MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
It seems to be the same thing when I try to use that approach in my code. – utdiscant Jan 18 '11 at 15:16
up vote 2 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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