1
$\begingroup$

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

  • 0
    If you remove vertex $x$ or $y$, you also remove edge $xy$, don't you?2012-02-24
  • 2
    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.2012-02-24
  • 0
    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 :)2012-02-24
  • 0
    @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 ...2012-02-24
  • 1
    @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$?2012-02-24
  • 0
    @Aryabhata: I guess not right ? :)2012-02-24
  • 0
    @PeeJay: You guess right :-)2012-02-24
  • 0
    So, PeeJay, if you now understand the situation, you can post an answer to your question (yes, this is not just allowed but encouraged) and then, if no one raises any significant objections over the next couple of days, you can accept your answer.2012-02-25
  • 0
    @GerryMyerson: thanks for the hint, I ll do that.2012-02-26

1 Answers 1

2

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.