I know a nonseparable graph is a connected graph with simply no cut vertices. And that a graph of order at least $3$ is nonseperable if and only if every two vertices lie on a common cycle.

I'm not sure how to advance from here though


Suppose $v$ is a cut vertex. Consider the smallest component $A$ of $G-v$. Each $a \in A$ has at most $(|A|-1)+1=|A| < \frac{n}{2}$ neighbours in $G$, contradiction.

  • $\begingroup$ Is the contradiction that $|A| < \frac{n}{2}$ when originally we assumed that $deg$ $v$ $\geq \frac{n}{2}$? $\endgroup$ – atherton Mar 6 '14 at 21:03
  • $\begingroup$ The contradiction is that $\deg a < n/2$ when we assumed that $\deg v \geq n/2$ for every vertex. $\endgroup$ – user133281 Mar 6 '14 at 21:05

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.