Skip to main content
added 72 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Below are some thoughts when $G$A counterexample is athe planar triangulationdual to the Tutte graph. Most of the credit goes to David Eppstein (see the comments below)

Let $G$ be the dual to the Tutte graph. Then $G$ is a planar triangulation. SupposeTowards a contradiction, suppose that $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$. ByBy Euler's Theoremformula, this implies that $G / C$ has only two vertices.

Conversely In particular, I had previously claimed that every set $C$ meeting each face once$(G / C)^*$ is a validHamiltonian. Since contraction setand deletion are dual operations, but that is in fact falsewe have $(G / C)^*=G^* \backslash C$. NoteThis implies that suchthe Tutte graph has a set $C$ does exist for every planar triangulation by Peterson's Theorem. See David Eppstein's comments belowHamilton cycle, which is a contradiction.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$. By Euler's Theorem, this implies that $G / C$ has only two vertices.

Conversely, I had previously claimed that every set $C$ meeting each face once is a valid contraction set, but that is in fact false. Note that such a set $C$ does exist for every planar triangulation by Peterson's Theorem. See David Eppstein's comments below.

A counterexample is the planar dual to the Tutte graph. Most of the credit goes to David Eppstein (see the comments below)

Let $G$ be the dual to the Tutte graph. Then $G$ is a planar triangulation. Towards a contradiction, suppose that $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$. By Euler's formula, this implies that $G / C$ has only two vertices. In particular, $(G / C)^*$ is Hamiltonian. Since contraction and deletion are dual operations, we have $(G / C)^*=G^* \backslash C$. This implies that the Tutte graph has a Hamilton cycle, which is a contradiction.

deleted 689 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$.

I claim that this condition is also sufficient for the existence of a contraction set.

Claim. If a planar triangulation $G$ has a set of edges $C$ such that each face of $G$ contains exactly one edge of $C$, then $G/C$ is a thick-tree.

Proof. Suppose $G$ has $n$ vertices. By By Euler's formula, $G$ has $3n-6$ edges and $2n-4$ faces. Since each edge is in exactly two faces, $C$ contains exactly $n-2$ edges. ThusTheorem, this implies that $G/C$$G / C$ has only two vertices, and so will automatically be a thick-tree as long as it contains no loops. Let $e_1, \dots, e_{n-2}$ be an arbitrary ordering of $C$. Since

Conversely, I had previously claimed that every set $C$ contains exactly one edge frommeeting each face of $G$, itonce is easy to show by induction on $k$a valid contraction set, but that no face of $G / \{e_1, \dots, e_{k}\}$ is a loopin fact false. $\square$

It is possible Note that all planar triangulations $G$ have such a set $C$ of edges, but I haven't thought too hard about that. If $G$ is a 3-colourable does exist for every planar triangulation, then it does indeed have such a set by $C$Peterson's Theorem. Just take a 3-colouring of $G$ and let $C$ be the set of edges with endpoints coloured 1 and 2 See David Eppstein's comments below.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$.

I claim that this condition is also sufficient for the existence of a contraction set.

Claim. If a planar triangulation $G$ has a set of edges $C$ such that each face of $G$ contains exactly one edge of $C$, then $G/C$ is a thick-tree.

Proof. Suppose $G$ has $n$ vertices. By Euler's formula, $G$ has $3n-6$ edges and $2n-4$ faces. Since each edge is in exactly two faces, $C$ contains exactly $n-2$ edges. Thus, $G/C$ has only two vertices, and so will automatically be a thick-tree as long as it contains no loops. Let $e_1, \dots, e_{n-2}$ be an arbitrary ordering of $C$. Since $C$ contains exactly one edge from each face of $G$, it is easy to show by induction on $k$ that no face of $G / \{e_1, \dots, e_{k}\}$ is a loop. $\square$

It is possible that all planar triangulations $G$ have such a set $C$ of edges, but I haven't thought too hard about that. If $G$ is a 3-colourable planar triangulation, then it does indeed have such a set $C$. Just take a 3-colouring of $G$ and let $C$ be the set of edges with endpoints coloured 1 and 2.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$. By Euler's Theorem, this implies that $G / C$ has only two vertices.

Conversely, I had previously claimed that every set $C$ meeting each face once is a valid contraction set, but that is in fact false. Note that such a set $C$ does exist for every planar triangulation by Peterson's Theorem. See David Eppstein's comments below.

deleted 341 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a small counterexample. Take a $6$-cycle $123456$, and add the edges $13, 35$, and $51$. Observe that it necessary to contract at least $4$ edges of the $6$-cycle, since otherwise a cycle with persist. But now one of the three triangles, $123$, $345$ or $561$ contains at least $2$ contracted edges, thereby creating a loop.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$.

I claim that this condition is also sufficient for the existence of a contraction set.

Claim. If a planar triangulation $G$ has a set of edges $C$ such that each face of $G$ contains exactly one edge of $C$, then $G/C$ is a thick-tree.

Proof. Suppose $G$ has $n$ vertices. By Euler's formula, $G$ has $3n-6$ edges and $2n-4$ faces. Since each edge is in exactly two faces, $C$ contains exactly $n-2$ edges. Thus, $G/C$ has only two vertices, and so will automatically be a thick-tree as long as it contains no loops. Let $e_1, \dots, e_{n-2}$ be an arbitrary ordering of $C$. Since $C$ contains exactly one edge from each face of $G$, it is easy to show by induction on $k$ that no face of $G / \{e_1, \dots, e_{k}\}$ is a loop. $\square$

It is possible that all planar triangulations $G$ have such a set $C$ of edges, but I haven't thought too hard about that. If $G$ is a 3-colourable planar triangulation, then it does indeed have such a set $C$. Just take a 3-colouring of $G$ and let $C$ be the set of edges with endpoints coloured 1 and 2.

Here is a small counterexample. Take a $6$-cycle $123456$, and add the edges $13, 35$, and $51$. Observe that it necessary to contract at least $4$ edges of the $6$-cycle, since otherwise a cycle with persist. But now one of the three triangles, $123$, $345$ or $561$ contains at least $2$ contracted edges, thereby creating a loop.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$.

I claim that this condition is also sufficient for the existence of a contraction set.

Claim. If a planar triangulation $G$ has a set of edges $C$ such that each face of $G$ contains exactly one edge of $C$, then $G/C$ is a thick-tree.

Proof. Suppose $G$ has $n$ vertices. By Euler's formula, $G$ has $3n-6$ edges and $2n-4$ faces. Since each edge is in exactly two faces, $C$ contains exactly $n-2$ edges. Thus, $G/C$ has only two vertices, and so will automatically be a thick-tree as long as it contains no loops. Let $e_1, \dots, e_{n-2}$ be an arbitrary ordering of $C$. Since $C$ contains exactly one edge from each face of $G$, it is easy to show by induction on $k$ that no face of $G / \{e_1, \dots, e_{k}\}$ is a loop. $\square$

It is possible that all planar triangulations $G$ have such a set $C$ of edges, but I haven't thought too hard about that. If $G$ is a 3-colourable planar triangulation, then it does indeed have such a set $C$. Just take a 3-colouring of $G$ and let $C$ be the set of edges with endpoints coloured 1 and 2.

Below are some thoughts when $G$ is a planar triangulation.

Let $G$ be a planar triangulation. Suppose $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$.

I claim that this condition is also sufficient for the existence of a contraction set.

Claim. If a planar triangulation $G$ has a set of edges $C$ such that each face of $G$ contains exactly one edge of $C$, then $G/C$ is a thick-tree.

Proof. Suppose $G$ has $n$ vertices. By Euler's formula, $G$ has $3n-6$ edges and $2n-4$ faces. Since each edge is in exactly two faces, $C$ contains exactly $n-2$ edges. Thus, $G/C$ has only two vertices, and so will automatically be a thick-tree as long as it contains no loops. Let $e_1, \dots, e_{n-2}$ be an arbitrary ordering of $C$. Since $C$ contains exactly one edge from each face of $G$, it is easy to show by induction on $k$ that no face of $G / \{e_1, \dots, e_{k}\}$ is a loop. $\square$

It is possible that all planar triangulations $G$ have such a set $C$ of edges, but I haven't thought too hard about that. If $G$ is a 3-colourable planar triangulation, then it does indeed have such a set $C$. Just take a 3-colouring of $G$ and let $C$ be the set of edges with endpoints coloured 1 and 2.

added 278 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
added 278 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
deleted 15 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading