What is a 2-regular graph?
What is a 2-regular graph? Is is the same thing as an 2-connected graph where a 2-connected graph is a graph G such that G-V ( G minus a vertex V) is still connected?
$\endgroup$ 12 Answers
$\begingroup$A regular graph is a graph where each vertex has the same degree. So a 2-regular graph is a graph where every vertex has degree 2. It is not the same as a 2-connected graph, since a 2-regular graph doesn't even have to be connected in the first place. For instance, it could be a graph whose components are two disconnected cycles. Conversely, the tetrahedral graph is 2-connected, but not 2-regular, as every vertex has degree $3$.
In general, a $k$-regular graph is one where every vertex has degree $k$.
$\endgroup$ 1 $\begingroup$So now you know what a $k$-regular graph is, but what do you think in particular a 2-regular graph looks like?
Certainly, all cycle graphs are 2-regular, but that's not all of them...what other graphs are 2-regular but not a cycle? (think about integer partitions of $n$)
$\endgroup$
