Skip to main content
MathOverflow

Return to Answer

directly embeded image
Source Link
GraffL
GraffL
  • 136
  • 4

Consider the following (connected) hypergraph: counter exampleA counter example

i.e. ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)

Consider the following (connected) hypergraph: counter example ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)

Consider the following (connected) hypergraph: A counter example

i.e. $V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)

added 257 characters in body
Source Link
GraffL
GraffL
  • 136
  • 4

Consider the following (connected) hypergraph: counter example ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)

Consider the following (connected) hypergraph: counter example ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Consider the following (connected) hypergraph: counter example ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)

Source Link
GraffL
GraffL
  • 136
  • 4

Consider the following (connected) hypergraph: counter example ($V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$)

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.