2
$\begingroup$

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?

  • 2
    Did you not try Wikipedia? http://en.wikipedia.org/wiki/Regular_graph2011-04-07

2 Answers 2

4

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

  • 1
    Yes your answer sparked my memory thank you.2011-04-07
0

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