<p>The first sentence on page 33 of Donald Knuth's <a href="https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming" rel="nofollow noreferrer">The Art of Computer Programming</a> (TAOCP) Vol. 4a reads:</p>
<blockquote>
<p>Furthermore, a hypergraph is equivalent to a <em>bipartite graph</em>  with vertex set <span class="math-container">$V \cup E$</span> and with the edge <span class="math-container">$v - e$</span> whenever <span class="math-container">$v$</span> is incident with <span class="math-container">$e$</span>.</p>
</blockquote>
<p>This is true when <span class="math-container">$V$</span> and <span class="math-container">$E$</span> are disjoint - which holds for non-pathological examples. But, using the <a href="https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals" rel="nofollow noreferrer">von Neumann definition of an ordinal</a> (where <span class="math-container">$0 = \emptyset$</span> and <span class="math-container">$n = \{0,...,n-1\}$</span> for all positive integers <span class="math-container">$n$</span>), a counterexample to this sentence can be constructed.</p>
<p>Let <span class="math-container">$0 = \emptyset$</span> and <span class="math-container">$1 = \{0\}$</span> and <span class="math-container">$2 = \{0, 1\}$</span>. Let <span class="math-container">$V = \{0, 1, 2\}$</span> and <span class="math-container">$E = \big\{  \{0\}, \{0,1\}  \big\}$</span>. Then we have the unusual situation that <span class="math-container">$E \subseteq V$</span>. So <span class="math-container">$V \cup E = V$</span>. The graph resulting from this hypergraph is the complete graph on <span class="math-container">$V = V \cup E = \{0, 1, 2\}$</span>, which is not bipartite.</p>
<p>A while ago, I sent this to the e-mail address indicated for submitting errors in TAOCP. So far I haven't heard back, which can have several reasons:</p>
<ol>
<li>What I perceive as a counterexample above is not a counterexample because it contains an error (which one?).</li>
<li>The counterexample is so weird it doesn't really count as a counterexample.</li>
<li>The counterexample, or a similar one, has already been submitted by somebody else.</li>
<li>The e-mail address is only checked rarely, if at all.</li>
</ol>
<p>I am grateful for any input on this!</p>

CC BY-SA 4.0
2024-02-14T11:55:02.557Z
This is not a counterexample, but being deliberately obtuse. It's obvious the union is meant to be disjoint union.
Emil Jeřábek
CC BY-SA 4.0
2024-02-14T13:10:37.230Z
Either it is mathematically valid, or it isn't. If you find a mathematical error in my argument, I would be very interested in learning about it. I checked the whole hypergraph chapter; disjointness is not mentioned explicitly, so only spiritually gifted people can make an educated guess about Donald Knuth's internal state at the time of writing the chapter.
Dominic van der Zypen
CC BY-SA 4.0
2024-02-14T13:17:59.043Z
When it comes to interpreting the US constitution, there are "textualists" (focusing on what words are in the text, and their ordinary meaning), and "intentionists" (interested in what the intentions of the writers of the law may have been). When it comes to mathematics, I have a textualist leaning.
Dominic van der Zypen
CC BY-SA 4.0
2024-02-14T14:23:45.547Z
Thanks for your comment @NealYoung . Knuth defines a (not necessarily bipartite) graph as a tuple $(V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{v,w\}:v\neq w \in E\}$, and he calls such a graph *bipartite* if there is $X\subseteq V$ such that for all $e\in E$ we have $e\cap X \neq \emptyset$ and $e\cap (V\setminus X) \neq \emptyset$. The triple notation is not used.
Dominic van der Zypen
CC BY-SA 4.0
2024-02-14T14:29:41.757Z
Yes, Knuth is glossing over something.  By [definition](https://mathworld.wolfram.com/CompleteBipartiteGraph.html) the two parts $U$ and $W$ of a bipartite graph $G'=(U, W, E')$ must be disjoint.  And a graph $G=(V,E)$ can have $V\cap E \ne \emptyset$.  E.g. consider $V=\{0, 1, (0,1)\}$ and $E=\{(0, 1), (0, (0, 1))\}$.  That being said, Knuth's books are not intended to be machine-verifiable proofs, they are expository.  Assuming that the given graph has $V\cap E = \emptyset$, as graphs in TCS generally do, is not an error, but an expository choice.  Most readers will understand the intention.
Neal Young
CC BY-SA 4.0
2024-02-14T14:35:37.930Z
[and...] _All_ texts _necessarily_ assume some shared context between the reader and author.  If a reader does not understand the assumed context, that does not mean that the text "isn't mathematically valid".  That readers generally do understand such texts is perhaps evidence that most of us, even the ordinary ones, must indeed be spiritually gifted in some useful way that is interesting to ponder.
Neal Young
CC BY-SA 4.0
2024-02-14T14:50:57.427Z
Since the text would become perfectly correct if a *dot* were placed over the $\cup$ sign, which is clearly the intended reading, this is, at worst, a *trivial typo*. Not an *error* that would warrant an email exchange.
Emil Jeřábek
CC BY-SA 4.0
2024-02-15T11:38:57.577Z
@DominicvanderZypen Maybe calling it an error might be off-putting to some. If you think the text specifying that the union is a disjoint one will be helpful to  readers, then maybe just say that.
mathworker21
CC BY-SA 4.0
2024-02-15T15:23:58.733Z
Good point @mathworker21
Dominic van der Zypen
CC BY-SA 4.0
2024-02-20T17:29:17.933Z
Another point: Notice that Knuth welcomes feedback also to small errors, like typos etc. and eagerly corrects these if he agrees that it is an error. However, he processes emails in bulk, so it may well be that you will have to wait for some weeks, or even months until you get an answer. Delay does not imply anything about your request, but is simply caused by his way of working on TAOCP.
Hermann Gruber
CC BY-SA 4.0
2024-02-21T10:54:46.523Z
Thanks @HermannGruber for this feedback!
Dominic van der Zypen
<graph-theory><bipartite-graphs><hypergraphs>
Error in TAOCP 4a on the bipartite graph constructed from a hypergraph
Dominic van der Zypen
# Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

(Asked by: username_0 on 2024-02-14)

The first sentence on page 33 of Donald Knuth's [The Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming) (TAOCP) Vol. 4a reads:

> Furthermore, a hypergraph is equivalent to a *bipartite graph* with vertex set $V \cup E$ and with the edge $v - e$ whenever $v$ is incident with $e$.

This is true when $V$ and $E$ are disjoint - which holds for non-pathological examples. But, using the [von Neumann definition of an ordinal](https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals) (where $0 = \emptyset$ and $n = \{0,...,n-1\}$ for all positive integers $n$), a counterexample to this sentence can be constructed.

Let $0 = \emptyset$ and $1 = \{0\}$ and $2 = \{0, 1\}$. Let $V = \{0, 1, 2\}$ and $E = \big\{ \{0\}, \{0,1\} \big\}$. Then we have the unusual situation that $E \subseteq V$. So $V \cup E = V$. The graph resulting from this hypergraph is the complete graph on $V = V \cup E = \{0, 1, 2\}$, which is not bipartite.

A while ago, I sent this to the e-mail address indicated for submitting errors in TAOCP. So far I haven't heard back, which can have several reasons:

1. What I perceive as a counterexample above is not a counterexample because it contains an error (which one?).
2. The counterexample is so weird it doesn't really count as a counterexample.
3. The counterexample, or a similar one, has already been submitted by somebody else.
4. The e-mail address is only checked rarely, if at all.

I am grateful for any input on this!

**Tags:** graph-theory, bipartite-graphs, hypergraphs

> **Comments:**
> **username_1**: This is not a counterexample, but being deliberately obtuse. It's obvious the union is meant to be disjoint union.  
> **username_0**: Either it is mathematically valid, or it isn't. If you find a mathematical error in my argument, I would be very interested in learning about it. I checked the whole hypergraph chapter; disjointness is not mentioned explicitly, so only spiritually gifted people can make an educated guess about Donald Knuth's internal state at the time of writing the chapter.  
> **username_0**: When it comes to interpreting the US constitution, there are "textualists" (focusing on what words are in the text, and their ordinary meaning), and "intentionists" (interested in what the intentions of the writers of the law may have been). When it comes to mathematics, I have a textualist leaning.  
> **username_0**: Thanks for your comment @NealYoung . Knuth defines a (not necessarily bipartite) graph as a tuple $(V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{v,w\}:v\neq w \in E\}$, and he calls such a graph *bipartite* if there is $X\subseteq V$ such that for all $e\in E$ we have $e\cap X \neq \emptyset$ and $e\cap (V\setminus X) \neq \emptyset$. The triple notation is not used.  
> **username_2**: Yes, Knuth is glossing over something.  By [definition](https://mathworld.wolfram.com/CompleteBipartiteGraph.html) the two parts $U$ and $W$ of a bipartite graph $G'=(U, W, E')$ must be disjoint.  And a graph $G=(V,E)$ can have $V\cap E \ne \emptyset$.  E.g. consider $V=\{0, 1, (0,1)\}$ and $E=\{(0, 1), (0, (0, 1))\}$.  That being said, Knuth's books are not intended to be machine-verifiable proofs, they are expository.  Assuming that the given graph has $V\cap E = \emptyset$, as graphs in TCS generally do, is not an error, but an expository choice.  Most readers will understand the intention.  
> **username_2**: [and...] _All_ texts _necessarily_ assume some shared context between the reader and author.  If a reader does not understand the assumed context, that does not mean that the text "isn't mathematically valid".  That readers generally do understand such texts is perhaps evidence that most of us, even the ordinary ones, must indeed be spiritually gifted in some useful way that is interesting to ponder.  
> **username_1**: Since the text would become perfectly correct if a *dot* were placed over the $\cup$ sign, which is clearly the intended reading, this is, at worst, a *trivial typo*. Not an *error* that would warrant an email exchange.  
> **username_3**: @DominicvanderZypen Maybe calling it an error might be off-putting to some. If you think the text specifying that the union is a disjoint one will be helpful to  readers, then maybe just say that.  
> **username_0**: Good point @username_3  
> **username_4**: Another point: Notice that Knuth welcomes feedback also to small errors, like typos etc. and eagerly corrects these if he agrees that it is an error. However, he processes emails in bulk, so it may well be that you will have to wait for some weeks, or even months until you get an answer. Delay does not imply anything about your request, but is simply caused by his way of working on TAOCP.  
> **username_0**: Thanks @HermannGruber for this feedback!  

---

## 0 answers

