## What’s the name of graphs with each vertex contained in a cycle?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

A tree is a graph with no vertex contained in a cycle.

A non-tree is a graph with some vertex contained in a cyle.

What's the name of graphs with each vertex contained in a cycle?

-

1
I'm wondering why no one had voted up this question (until I just did), even though people were answering and voting up answers. – Jonas Meyer Jan 11 2010 at 1:34

## 5 Answers

Undirected graphs in which every edge is contained in a cycle are called bridgeless or 2-edge-connected. But I don't know of a word for the analogous concept for vertices.

-
Could this mean that this is an unfruitful concept (since if it were fruitful it would have a name X, e.g. to be able to formulate statements like "all graphs that are X are Y" or vice versa?) The other way round: Do you know an interesting theorem which implies graphs with the above mentioned property? – Hans Stricker Jan 11 2010 at 0:48
If this graph property was fruitless: How could this be explained, compared to the "unreasonable" fruitfulness of trees? – Hans Stricker Jan 11 2010 at 0:52

6
Nice pun! Was it intentional? – Qiaochu Yuan Jan 11 2010 at 1:56
I guess it was not (if you refer to the "fruits" of "trees"). But can you - who has used the term "unreasonable" too (in another context) - appreciate the question? – Hans Stricker Jan 11 2010 at 2:21
@David: If every edge is contained in a cyle, doesn't every vertex have to be contained in a cycle, too? And vice versa? That is, isn't the concept "self-dual"? – Hans Stricker Oct 29 at 18:17
show 4 more comments

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

I don't know a name, but I'll give you a different characterization. Biconnectivity is sufficient but too strong, while "having minimum degree at least 2" is necessary but too weak. I'm almost certain this is a necessary and sufficient condition:

$G$ has minimum degree at least 2, and if v is a cutvertex of $G$, then there is some new connected component of $G - v$ with at least two vertices adjacent to v.

Here's a proof of sufficiency: If v is not a cutvertex of $G$, then pick any two vertices adjacent to v. There's a path between them not going through v (since $G - v$ is connected), so v is contained in a cycle.

If v is a cutvertex of $G$, then pick the two vertices adjacent to v that are in the same connected component of $G - v$. There's a path between them that extends to a cycle containing v.

Now, a proof of necessity. Suppose that $G$ has a cutvertex $v$ whose removal does create deg(v)-1 new connected components. Then $v$ can't lie in a cycle. (This is easy to check.)

This characterization is equivalent to: Removing any vertex of degree d increases the total number of connected components by at most $d-2$. Some generalization of this property may have a name.

-

Thanks. Please see my comments to David's answer. They apply also to yours. – Hans Stricker Jan 11 2010 at 1:07
How can vertices of G-v be adjacent to v? – Hans Stricker Jan 11 2010 at 1:10
Sorry, I meant adjacent in the original graph. – Harrison Brown Jan 11 2010 at 1:16
Sorry for my part, I should have understood it this way. (You treat the one counter-example of David below - the 8-graph - and we are done?) – Hans Stricker Jan 11 2010 at 1:24

These are the graphs that admit "vertex cycle covers". http://en.wikipedia.org/wiki/Vertex_cycle_cover

-

+1, even if this is not really a name but just another characterization. (At least it's something to google for.) – Hans Stricker Jan 25 2010 at 7:27

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

Every vertex of $G$ is contained in a block of $G$ which is not a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.

-

2-connected or biconnected

-

of course, this works only for connected graphs. – Klingonesque Jan 11 2010 at 0:32
A figure-eight graph has every vertex in a cycle but is not biconnected. – David Eppstein Jan 11 2010 at 0:36
Even if those graphs were biconnected, their biconnectivity would have to be proved, but would not be the defining property, for which I am looking for a name. – Hans Stricker Jan 11 2010 at 0:55
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9498828649520874, "perplexity_flag": "middle"}