1
$\begingroup$

I've come across this theorem and I don't understand a definition used in it:

A graph of order at least $3$ is nonseparable iff every two vertices lie on a common cycle

What's a common cycle? Is it two cycles in a graph that share an edge or a point? Or is this just saying that they lie on the same cycle?

$\endgroup$
2
  • 3
    $\begingroup$ It's just saying that they lie on the same cycle. Note, however, this is different from saying that every pair lies on the same cycle. $\endgroup$ Commented Aug 16, 2017 at 18:33
  • 2
    $\begingroup$ In the definition you quoted, the word "common" is not a technical term; it is used in its ordinary English meaning. Should we correct the misspelling of "vertices" or was it misspelled "verticies" in the unnamed source that you are quoting? $\endgroup$
    – bof
    Commented Aug 16, 2017 at 21:09

1 Answer 1

3
$\begingroup$

This just means that for any vertices $v$ and $w$, there exists a cycle $C$ which contains both $v$ and $w$. The word "common" is informal and merely emphasizes that this cycle $C$ depends on $v$ and $w$ and is shared by both of them (you could say that being in $C$ is a property that is common to $v$ and $w$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .