

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


