I want to prove that: for any simple, connected graph there is at least one node whose removal results in a connected graph. Here is my proof:

  • Suppose that a graph $G$ is simple connected graph with $\delta(G)$ is the minimum degree of the vertices. If $\delta(G)=1$ then there is a node with one edge, and removing this node with its edge keeps $G$ connected

  • If $\delta(G) \ge 2$, then $G$ cannot be a tree, and we must have a cycle in the graph $G$, as every tree has at least two leaves which means $\delta(G) =1$ for trees. Now suppose that the cycle is defined as $C= (v_0,v_1,\cdots,v_k,v_0)$. Then, removing the node $v_i$ from $C$ where $deg(v_i)$ is the lowest degree of the nodes in this cycle will certainly keep the graph connected.

    This concludes the proof.

Is this a correct and complete proof?

  • 2
    $\begingroup$ to clarify: "k-connected" means (by definition) that removing any k-1 vertices still leaves the graph connected. So "1 connected" means that removing 0 vertices leaves the graph connected. Yes? $\endgroup$ – lulu Jul 25 '15 at 14:30
  • $\begingroup$ @lulu @ wythagoras, I've updated the question to adhere the definition of the Wolfram Mathworld. $\endgroup$ – M.M Jul 25 '15 at 14:34
  • $\begingroup$ But...what is there to prove? Removing $0$ vertices leaves the graph unchanged. $\endgroup$ – lulu Jul 25 '15 at 14:35
  • $\begingroup$ I've updated the question, I meant removing 1 node keeps the graph connected. $\endgroup$ – M.M Jul 25 '15 at 14:36
  • 1
    $\begingroup$ But the statement "any connected graph is 2-connected" is nonsense. Just take a straight line path with at least 3 vertices. $\endgroup$ – lulu Jul 25 '15 at 14:41

No. You misunderstood the definition of 2-connected. This says that you can't remove a vertex such that the graph becomes unconnected. You have merely proven that there exists a vertex that can be removed such that the graph remains connected.

The claim is not true either. For this, consider the 3-path.

  • $\begingroup$ Thanks for the clarification, I've updated the question based on your comment and lulu's comment. $\endgroup$ – M.M Jul 25 '15 at 14:48
  • $\begingroup$ @M.M Yes, I already thought that. But I can't quite follow the argument. $\endgroup$ – wythagoras Jul 25 '15 at 14:49
  • $\begingroup$ what part exactly is not clear? $\endgroup$ – M.M Jul 25 '15 at 14:58

Not sure I am clear on your proof. it is not true that removing a minimal valence node from a cycle keeps the graph connected: think of a "benzene molecule", a graph consisting of a cycle and one node hanging off each cycle node.

To prove the statement you want: choose a node P at random. For any node V define L(V) to be the length of a minimal path from P to V. Then you can remove any node, W, with maximal L(W). (if Q is any other node then the shortest path from P to Q can't go through W, as that would make L(Q) > L(W))

  • $\begingroup$ For the benzene molecule, there are $6$ nodes with degree = 1, so you can remove them based on step one in my proof, right? $\endgroup$ – M.M Jul 25 '15 at 16:01
  • $\begingroup$ Of course, but the logic of your proof was: either the graph has a node of valence one (trivial case) or else it has a cycle. That much is true. But then you say you have a way to handle cycles, but I don't see how your method works (the benzene example would seem to be a counterexample to your method). Your claim is true (and I believe my proof is valid) but I think your proof is incomplete. $\endgroup$ – lulu Jul 25 '15 at 19:50
  • $\begingroup$ I have a way to handle cycles if there is no nodes with degree equals one. So, for the benzene molecule the proof works because the graph has at least one node with degree one, so the graph is not a counter example. $\endgroup$ – M.M Jul 25 '15 at 20:49
  • $\begingroup$ No...it's easy to avoid valence 1, instead of simple H in my benzene example, suppose I had a little cycle (or just have double bonds, if you haven't ruled them out). Your method claims to handle cycles in general, but I have no idea how. $\endgroup$ – lulu Jul 25 '15 at 20:55
  • 1
    $\begingroup$ Specifically: you claim (or appear to claim) that you can always delete at least one element in any cycle and this is plainly false (just take a simple 3 cycle with nodes A, B, C, and attach some nodes to each. Clearly you can not delete A or B or C). $\endgroup$ – lulu Jul 25 '15 at 20:58

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.