Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

For a simple undirected connected Graph $G(V,E)$ I say the edge $xy \in E(G)$ disconnects G if the resulting graph G' does not have a path from every vertex to every other vertex.

Now suppose I have such an edge xy, such that $G-(xy)$ is disconnected. I am wondering whether I can always get a disconnected Graph $G'$ similarly by removing the vertex x or y (just one of them) and all corresponding edges in this situation ?

I need to be careful obviously, as removing the egde $(xy)$ might have created a component consisting of just x or y alone, so if I tried to get a disconnected G' by removing that vertex I might have failed ! However if this problem occurs with both vertices then after removing one I end up with a trivial Graph of 1 vertex, which I define to be disconnected for my purposes, and if it only occurs with 1 vertex, then I just remove the other one, which should give me a disconnected Graph as desired again right ?

My Question is, whether this analysis of the situation is correct; i.e. given that an edge xy will give me disconnected graph $G-{(xy)}$ then I will also be able to obtain a disconnected graph $G-(x)$ or $G-(y)$.

share|cite|improve this question
If you remove vertex $x$ or $y$, you also remove edge $xy$, don't you? – Aryabhata Feb 24 '12 at 21:19
The one-vertex graph is not disconnected. But the rest of your argument looks fine to me. By the way, I think you mean "removing the vertex $x$ or $y$" in your second paragraph. – Rahul Feb 24 '12 at 21:31
thanks, just corrected that, it should indeed have been vertices. I know the trivial one is connected strictly speaking, but for my purposes I define it to be disconnected :) – Beltrame Feb 24 '12 at 21:42
@Aryabhata: you do indeed, but you might have removed a vertex that was essential to get a disconnected graph I think. Consider a complete Graph with 3 vertices and attach an edge and a vertex at one end for instance, now consider that last edge ... – Beltrame Feb 24 '12 at 22:12
@PeeJay: Yes. If $G$ is connected with at least $3$ vertices, and $xy$ is an edge, can both $x$ and $y$ be of degree $1$? – Aryabhata Feb 24 '12 at 22:20
up vote 1 down vote accepted

So it turns out the analysis given is correct, since we can always remove a vertex with degree greater then 1 as long as G is connected with $|V(G)| \ge 3 $, and the special case where the size of G is smaller is covered by my special case definition.

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.