Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?

Question

Consider simple bridgeless cubic planar graphs.

• Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?

• If not, does anyone know of an counterexample?

• More generally: each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even order. But is there an upper bound of the number of these components?

Answer 1

If one takes a planar cubic non-Hamiltonian graph, and takes the vertex connect sum of 3 copies, then it cannot have such a 2-factor. It's not hard to check that a vertex connect sum of such graphs is also non-Hamiltonian. If there were a 2-factor with only two components, it would have to traverse two of the 3 edges connecting one of the pairs of subgraphs. But then one of the two sides must be Hamiltonian, a contradiction.

Here's a picture of a vertex sum of planar cubic graphs:

Answer 2

_{This is not an answer, yet a very relevant comment which to give with due precision is not conveniently possibly via the comment boxes.}

Worth pointing out: if the claim

each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even length.

in the original OP is true¹, then the hypothesis 'planar' in the OP is indispensable, because for the (non-planar) Petersen graph, the conclusion is false. More precisely, the Petersen graph is a simple bridgeless cubic graph, which

• is widely-known to be non-Hamiltonian,
• has the property that each of the 2-factorizations (which must exist for general reasons, by Petersen's theorem) consists of the disjoint union of two 5-circuits. ${}\qquad\qquad$ (claim.0)

(Hence, in the OP's terminology, the 'lengths of the components' of the 2-factorization both have odd length.)

Proof of (claim). Each component of a 2-factorization is a graph-theoretic cycle(=:circuit). Any circuit has length at least three. The Petersen graph does not contain any 3-circuit. Hence the only relevant partitions of 10 are $10 = 4+6$ and $10=5+5$.

Moreover, while the Petersen graph does contain both 4-circuits an 6-circuits, it

• does not contain any 2-factorization of the type (4-circuit)$\sqcup$(6-circuit) ${}\qquad\qquad$ (claim.1)

A proof of (claim.1) follows e.g. from what is described in

https://math.stackexchange.com/users/91818/rebecca-j-stones, the number of copy of 6-cycles in petersen graph, URL (version: 2015-05-29): https://math.stackexchange.com/q/1303377

from which I take the illustration

Briefly, a proof of (claim.1) is: fix the 'inner' 5-set in the 'usual' drawing of the Petersen graph; any 6-circuit must intersect the cut defined by the fixe 5-set in an even number of edges; it cannot intersect it in 0 or 4 edges, the latter since all the cut-edges form a matching, so if the 6-circuit did intersect the cut in 4 edges, then the 6-circuit would have to have at least 8 edges, which is impossible. So the 6-circuit must intersect the cut in precisely two edges. The rotational symmetries of the Petersen-graph now suffice (it has more symmetries...) to see that the 6-circuit up to isomorphism must look like one of the 6-circuits in Stones' illustrations, and then the non-existence of the 4-circuit in the putative 2-factorization follows by inspection of Stones' illustrations.

This completes a proof of (claim.1), and hence also of (claim.0).

To reiterate: if the above-cited claim in the OP is true, then the assumption of planarity is essential for its truth.

¹ _{Which I for one do not find evident. It seems not to follow from superficial calculations alone.}

Answer 3

While the accepted answer appears correct, and has nice constructive and even functorial properties, it does not (yet) address the generalized question

But is there an upper bound of the number of these components?

in the OP, and it now occurred to me that one can disprove this easily (albeit non-constructively), using old research literature on the statistics of path- and circuit-lengths in planar graphs. So here is another answer.

Since I prefer using a standard technical term, let me first point out that

'2-factor each of whose components has even order'

(also called a 'weak Hamiltonian' in Definition 2.1 of the article arXiv:1505.04487 linked to by the OP)

has been called

Tait subgraph

by both Dénes Kőnig in (an English translation of) his book Theory of Finite and Infinite Graphs, and by W.T. Tutte in the following excerpt from his book 'Graph Theory', Cambridge University Press, 2001,

so I will use 'Tait subgraph'$=$'2-factor each of whose components has even order' in the following.

Now the answer proper.

Proposition(number of connected components of Tait subgraphs is not absolutely bounded for the class of all polyhedral graphs) . There does not exist any absolute constant $b$ such that every finite vertex-3-connected cubic planar simple undirected graph contains a Tait subgraph with at most $b$ components.

(Note that 'vertex-3-connected' implies 'bridgeless', so this even answers a weakening of the question in the OP, wherein only 'bridgeless' was assumed.)

Proof (by contradiction). If there were an absolute, constant bound $b\in\mathbb{Z}$ such that every $n$-vertex bridgeless cubic planar simple undirected graph contained a Tutte subgraph with at most $b$ components, then evidently (by the crudes counting argument imaginable) this would mean that

(assumption) every $n$-vertex bridgeless cubic planar simple undirected graph contains a circuit of length at least $\frac{1}{b} n$, in other words, has circumference at least that large.

Yet it is amply documented in the research literature that this is impossible.

We define some terminology.

If $\mathbb{K}$ is a class of graphs, a number $\sigma$ is called a shortness exponent for $\mathbb{K}$ if and only if there exists a constant $c>0$ and a sequence $G\colon\omega\rightarrow\mathbb{K}$ such that

• all $G_i$ are pairwise non-isomorphic (which implies, since we are speaking about finite graphs only, that $\lvert G_i\rvert\xrightarrow[]{i\to\infty}\infty$)

• $\mathrm{cir}(G_i)\leq c\cdot \lvert G_i \rvert^\sigma$.

Let $\sigma(\mathbb{K}) = \inf\{\sigma>0\colon\text{$\sigma$ is a shortness exponent for $\mathbb{K}$}\}$.

Improving on a well-known result of Grünbaum and Motzkin, it is proved in

Branko Grünbaum, Hansjoachim Walther, Shortness exponents of families of graphs, Journal of Combinatorial Theory, Series A, Volume 14, Issue 3, 1973, Pages 364-385

that $\sigma(\{\text{all $3$-regular vertex-$3$-connected plane graphs in which each face is bounded by at most $15$ edges}\}) \leq \frac{\log 22}{\log 23} < 0.98583$

Fully spelled out, and taking (assumption) into consideration, this implies that there exists an absolute constant $c>0$ and a sequence $(G_i)_{i\in\omega}$ consisting only of $3$-regular vertex-$3$-connected graphs each of whose faces is bounded by at most $15$ edges such that

$\lvert G_i\rvert\xrightarrow[]{i\to\infty}\infty$, (growth)

and

for all $i\in\omega$, $\frac{1}{b}\lvert G_i\rvert \leq \mathrm{cir}(G_i)\leq c \cdot \lvert G_i\rvert^{0.99}$,

where in the latter for the lower bound (assumption) was used.

This implies that

for all $i\in\omega$, $\lvert G_i\rvert^{0.01} \leq b\cdot c$,

and this is impossible, no matter how large the constants $b$ and $c$ may be, because of (growth).

This completes the proof of the proposition.

(Incidentally, Grünbaum and Motzkin proved a statement similar to the one used above for graph-theoretic paths instead of graph-theoretic circuits, which allows for even stronger disproofs of the conjecture implicit in the OP.)

Again, this is a non-constructive argument, using real analysis, and Ian Agol's answer appears to have the nice property of being what one might call a 'constructive disproof'. Yet whether it gives the no-bound-whatsoever statement, too, remains to be checked.