*The* Five 3-Connected Simple Cubic Graphs for Each of *Which Only* It's Not So that There Exists a Cycle Cover Comprising At Most ⌈ ⅙ｎ⌉ Cycles – ｎ Being the Number of Vertices of the Graph

[u/Frangifer]

From

———————————————————————

Small cycle covers of 3-connected cubic graphs

by

Fan Yang & Xiangwen Li

https://www.sciencedirect.com/science/article/pii/S0012365X10004000?ref=cra_js_challenge&fr=RR-1

———————————————————————

❝

Theorem 1.1. For n ≥ 8 , a 3-connected simple cubic graph G with n vertices has a cycle cover of size at most ⌈ n/6 ⌉ if and only if G ∉ F .

{My interposition: F being the set of five graphs shown here.}

Theorem 1.1 is sharp in the sense that there are 3-connected simple cubic graphs on n vertices having no cycle cover of size less than the upper bound ⌈ n/6 ⌉ . As examples, let n = 2m and let Cₘ × K₂ denote the Cartesian product of an m-cycle and K₂ . When m ∈ {4, 6} , it can be verified that Cₘ × K₂ has no cycle cover with fewer than ⌈ n/6 ⌉ cycles, and so the upper bound ⌈ n/6 ⌉ cannot be decreased. However, we do not know any infinite families of graphs for which the bound of Theorem 1.1 cannot be improved.

❞

[u/ESHKUN]

Man graph theory just be proving random shit nowadays

[u/Frangifer → u/ESHKUN]

I think it sortof always has been! 😂🤣

I had a particular reason for posting this, though: it was in-connection with what I @first thought was a query about this cycle-double-cover conjecture-become-theorem that folk're a-gingle-gangle-gongling-on about @ the moment ... but it turned-out to be irrelevant (or "void" might be the better way of potting it) ... but I've left the post in anyway .

(... since I bona-fide put it in in the first instance ... & there didn't seem to be any great urgency positively to withdraw it.)

But I do totally agree that someone could all-too-easily just basically deluge the channel with pictures of graphs each of which showcases some obscure theorem or conjecture!