# Accelerate `is_cactus()`

Reported by: Owned by: gh-r-barnes minor sage-9.1 graph theory cactus João Tavares David Coudert N/A ac1cf88 (Commits) ac1cf884ade760e719e48a5c44461e7065370c9a

### Description

This proof could be used to accelerate `is_cactus()` by providing a quick O(1) check that can detect a large class of graphs which are not cactuses. This, in turn, would be helpful for situations where `is_cactus()` is applied to large graphs.

### comment:1 Changed 18 months ago by gh-r-barnes

(I have not yet found an academic citation for the theorem.)

### comment:2 Changed 18 months ago by dcoudert

• Component changed from group theory to graph theory

If you are not able to double check the proof, it's better to find a reference (article, school book, etc.). This looks like a class exercise...

### comment:3 Changed 18 months ago by dcoudert

Actually, fill free to add the test without reference. This result is well known and often used as an exercise. Furthermore, this is a tight bound and we have graphs reaching it.

```sage: for n in range(1, 10):
....:     G = graphs.FriendshipGraph(n)
....:     G.size() == 3 * (G.order() - 1) / 2
....:
True
True
True
True
True
True
True
True
True
sage: for _ in range(10):
....:     G = graphs.RandomBlockGraph(10, 3)
....:     G.size() == 3 * (G.order() - 1) / 2
....:
True
True
True
True
True
True
True
True
True
True
```

### comment:4 Changed 13 months ago by embray

• Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

### comment:5 Changed 11 months ago by gh-tabus

• Branch set to u/gh-tabus/accelerate__is_cactus___

### comment:6 Changed 11 months ago by gh-tabus

• Status changed from new to needs_review

New commits:

 ​ac1cf88 `Added the necessary condition check`

### comment:7 Changed 11 months ago by dcoudert

• Reviewers set to David Coudert

Please add your full name in the field `Authors` of this page.

### comment:8 follow-up: ↓ 9 Changed 11 months ago by gh-tabus

• Authors set to João Tavares

### comment:9 in reply to: ↑ 8 Changed 11 months ago by gh-tabus

Replying to gh-tabus: Here it is. Is there anything else that should be done?

### comment:10 Changed 11 months ago by dcoudert

• Status changed from needs_review to positive_review

For this simple test, this is enough.

### comment:11 Changed 11 months ago by vbraun

• Branch changed from u/gh-tabus/accelerate__is_cactus___ to ac1cf884ade760e719e48a5c44461e7065370c9a
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.