4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What is your definition of 2-factorization? My understanding is that a 2-factorization is a partition of the edge set into 2-factors. This does not seem possible in a cubic graph, since once you find a 2-factor and remove the edges you are left with a 1-factor. $\endgroup$ – fidbc Aug 22 '17 at 23:55
  • $\begingroup$ A 2-factor is a regular subgraph of degree 2 containing all vertices of the original graph. The complement is indeed a 1 factor. $\endgroup$ – Jimmy Dillies Aug 23 '17 at 1:44
  • 1
    $\begingroup$ Dear @JimmyDillies: I made several edits to the OP. If you have reasons to object, please correct or roll back. Most seriously, the paragraph starting with "Stated otherwise" was confusing (to me), at least one the level of English-composition: it left it unclear whether you claimed that what comes next is equivalent to what comes before (which it not really is). $\endgroup$ – Peter Heinig Aug 23 '17 at 7:33
  • 1
    $\begingroup$ If one takes the question strictly literally, the answer is no: the infinite hexagonal grid is cubic bridgeless planar, yet does not admit any 2-factorization with an even number of components, for the boring cardinality reason that each 'factor' is by definition finite, so there must be $\aleph_0$-many components in any factorization, and $\aleph_0$ is not usually considered 'even'. Of course, this is not what the OP intends. I will not make this an answer, rather edit the OP. Yet it shows that any proof must make use of finiteness here. $\endgroup$ – Peter Heinig Aug 23 '17 at 7:45
4
+50
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ Technical comments for inexperienced readers: the use of "vertex connect sum" is correct. In view of the usual connected sum, which is similar yet not the same, the term "connect sum" may sound wrong, yet the term is used in this form in Knot Theory. And the modifier 'vertex' in 'vertex connect sum' is to distinguish it from the 'connect sum' which is used in Knot Theory, too, and in which it is an edge which gets deleted. Both operations are discussed in this paper of D. P. Thurston. $\endgroup$ – Peter Heinig Aug 25 '17 at 7:51
1
$\begingroup$

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 true1, 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

enter image description here

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.

1 Which I for one do not find evident. It seems not to follow from superficial calculations alone.

$\endgroup$
  • $\begingroup$ The claim is true; I discuss it in arXiv:1505.04487 and indeed requires planarity. The idea goes as follows. Take a 4-coloring of the faces of your cubic planar graph. Pick any two colors and look at the faces colored by these 2 colors. The border of these faces is is 2 factor where each cycle has even length. $\endgroup$ – Jimmy Dillies Aug 23 '17 at 19:39
1
$\begingroup$

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,

enter image description here

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.

$\endgroup$
  • $\begingroup$ Ian Agol's gives a constructive proof: $\endgroup$ – Jimmy Dillies Aug 27 '17 at 4:23
  • $\begingroup$ Let n(A) be the minimal number of components of a graph's Tait subgraphs, and let's denote by A' the vertex sum of three copies of A. Agol's answer shows that n(A')=3n(A)-2. By taking the iterated sequence A, A', (A')', ... one gets a family of planar cubic graphs with a strictly increasing number of components for its minimal Tait subgraph. $\endgroup$ – Jimmy Dillies Aug 27 '17 at 4:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.