TAOCP 7.1.4 Exercise 98

Let $G(x,y)$ be the Boolean function defined in (70), representing adjacency in an undirected graph on vertices ${1,\dots,n}$, where $G(x,y)=1$ iff there is an edge between $x$ and $y$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 98. ▶ [22] [22] In addition to (70), explain how to define the vertices ENDPT(x) of G that have degree ≤1. Also characterize PAIR(x, y), the components of size 2.

Verified: no
Solve time: 7m26s

Solution

Let $G(x,y)$ be the Boolean function defined in (70), representing adjacency in an undirected graph on vertices ${1,\dots,n}$, where $G(x,y)=1$ iff there is an edge between $x$ and $y$.

The degree of a vertex $x$ is expressed by the existence of neighbors $y$ such that $G(x,y)=1$. A vertex has degree $0$ or $1$ exactly when it does not have two distinct neighbors.

The condition “$x$ has degree $\le 1$” is equivalent to the negation of the existence of two distinct vertices both adjacent to $x$, that is,

$\neg \exists y \exists z ; (y \ne z \wedge G(x,y) \wedge G(x,z)).$

Using only Boolean operations and quantification over the vertex domain, this defines the characteristic function of the set of endpoints:

$\mathrm{ENDPT}(x) = \neg \exists y \exists z ; (y \ne z \wedge G(x,y) \wedge G(x,z)).$

Equivalently, separating the cases $y=z$ from $y\ne z$, this condition excludes the presence of two distinct incident edges and therefore allows degree $0$ and degree $1$ vertices while rejecting all vertices of degree at least $2$.

To characterize components of size $2$, consider a pair of distinct vertices $x$ and $y$ such that there is an edge between them and no other adjacencies for either endpoint. Such a pair forms a connected component of size $2$ exactly when the following three conditions hold:

  1. $x \ne y$,
  2. $G(x,y)=1$,
  3. both $x$ and $y$ have degree at most $1$.

Thus the Boolean predicate for such isolated edges is

$\mathrm{PAIR}(x,y) = (x \ne y) \wedge G(x,y) \wedge \mathrm{ENDPT}(x) \wedge \mathrm{ENDPT}(y).$

Correctness follows from the structure of degree constraints. If $\mathrm{PAIR}(x,y)$ holds, then $G(x,y)=1$ implies adjacency, and $\mathrm{ENDPT}(x)$ and $\mathrm{ENDPT}(y)$ ensure neither vertex is incident to any other edge, so the connected component containing $x$ and $y$ consists exactly of these two vertices. Conversely, if a component has size $2$, say ${x,y}$, then $x$ and $y$ are adjacent and have no other neighbors, so both satisfy $\mathrm{ENDPT}$ and the pair satisfies the formula above.

This completes the proof. ∎