HOME

So much for scientific visualisation

Show original manuscript

So much for scientific visualisation

An undirected graph without self-loops and without multiple edges contains a triangle if it has 4 vertices and 5 edges. the simplest proof observes that the graph in question is the complete 4-graph from which 1 edge has been removed: any triple vertices that does not contain both endpoints of the removed edge yields a triangle. If you insist on making a picture, you may consider

or

I would have asked quite a few people how they would prove the existence of a triangle with 4 vertices and 5 edges. The majority found itself observing both

and

seduced to make the “distinction” of whether the missing edge was a side or a diagonal.

A sobering observation!

Nuenen, 9 July 1991

prof. dr. Edsger W. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
USA