 |
or
|
 |
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
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
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
