for catherine j.

April 26, 2011 in Cool Tricks, Lectures Without Words

a recent post in KTM asked why
.
i know that one.

the “graph” in the upper right is K_4…
the “complete graph on 4 vertices”…
and has *6* (so-called) edges.

its “complement” (upper left) has *none*
of the edges. obviously there’s one
(so-called) *complete* graph having
all six possible edges and one “empty”
graph having *none* of the edges.

move down to the next couple lines:
the graphs having exactly *one* edge
match up in one-to-one fashion
with the graphs having *five* edges
(because “including five (edges)”, in this context,
is the same as “leaving out *one* (edge) out”.

so on for two-edge graphs.
each is the “complement”
(via the inclusion-exclusion principle
as hinted at a moment ago)
of a *four*-edge graph.

posting; gotta go to class.

Advertisement