Accelerate `is_cactus()`

[gh-r-barnes]

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

[gh-r-barnes]

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

[dcoudert]

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

[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

[embray]

Ticket retargeted after milestone closed

[gh-tabus]

New commits:

​ac1cf88

Added the necessary condition check

[dcoudert]

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

[gh-tabus]

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

[dcoudert]

For this simple test, this is enough.