Skip to main content
MathOverflow

Return to Answer

Bounty Ended with 50 reputation awarded by Jimmy Dillies
added 55 characters in body
Source Link
Ian Agol
Ian Agol
  • 68.8k
  • 3
  • 194
  • 358

If one takes a planar cubic non-Hamiltonian graphplanar 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

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

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

added figure
Source Link
Ian Agol
Ian Agol
  • 68.8k
  • 3
  • 194
  • 358

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

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.

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

Source Link
Ian Agol
Ian Agol
  • 68.8k
  • 3
  • 194
  • 358

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.