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

Such a gadget does not exist.

Proof for original vertex version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Proof for edited edge version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished edges. Let $M_1$ be a maximum weight matching which contains $x,y,z$, and let $M_2$ be a maximum weight matching which is disjoint from $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is adjacent to a degree 1 vertex, each of $x,y$ and $z$ must be end edges of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Such a gadget does not exist.

Proof. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Such a gadget does not exist.

Proof for original vertex version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Proof for edited edge version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished edges. Let $M_1$ be a maximum weight matching which contains $x,y,z$, and let $M_2$ be a maximum weight matching which is disjoint from $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is adjacent to a degree 1 vertex, each of $x,y$ and $z$ must be end edges of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Post Undeleted by Tony Huynh
Post Deleted by Tony Huynh
added 70 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Such a gadget does not exist.

Proof. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices of degree 1. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Such a gadget does not exist.

Proof. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices of degree 1. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Such a gadget does not exist.

Proof. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Such a gadget does not exist.

Proof. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices of degree 1. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).