THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |

Venn Graphs of Venn's General Construction

Here are the Venn dual graphs of Venn's general construction for
*n*=3,4,5, without coloured edges.
The red edges indicate the Hamilton cycle that is used in extending
to the next higher value of *n*.

How, in general, do you go from the dual graph *D* of
a Venn diagram, together with a Hamilton cycle
*H* in *G*, and get a new planar
dual *D'* of a Venn diagram of the
next higher order?
We now explain this process.
Note that *H* is a simple closed curve with an interior
and an exterior.

We illustrate the discussion on the expansion of *n*=4
to *n* = 5 as shown above.
Color the edges of *H* red, edges on the interior blue,
and edges on the exterior black.

- Each (black) vertex of
*D*is split into two vertices, one green and one blue, in*D'*. The blue vertices are in the interior, the red edges in the exterior. - Each blue edge in
*D*becomes a blue edge in*D'*connecting the corresponding blue vertices. - Each black edge in
*D*becomes a black edge in*D'*connecting the corresponding green vertices. - Each red edge in
*D*becomes a 4-cycle of red edges in*D'*, connecting either corresponding vertices or vertices of the same color.

Note that the red edges in *D'* give the prism of the Hamilton
cycle in *D*.

Peter Winkler provides a similar discussion in [Wi pg. 271].

THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |