Puzzle I

This is a graph. The nickname of this graph is K₅, but its full name is “The complete graph on 5 vertices”. Let me back up. The five numbered dots are the vertices. The lines connecting the vertices are called edges. Note that, contrary to appearances, the edges do not “cross”. The lines in that diagram which represent the edges do indeed cross, but the edges themselves are really just unordered pairs of vertices: {1,2}, {1,3}, {2,3}, etc. They do not have to be drawn as straight lines, nor do the vertices have to be drawn in the form of a regular pentagon. You can think of the edges as bungees that are connected to pairs of vertices. The graph would still be K₅, even if the vertices were shifted around, or the edges drawn squiggly, for instance to represent the graph in a way that does not depict the edges as “crossing” (although if you find a way to draw K₅ in a plane without crossed edges, the universe would certainly implode!).

Note that K₅ contains many triangles (or K₃, in graph theory parlance). The reason K₅ is considered to be a “complete” graph is that all possible edges are present; there are no two vertices which are nonadjacent (adjacent meaning connected by an edge). And because every possible edge is present, that also means that, for every possible selection of 3 of the 5 vertices, all of the edges between them (a triangle) are also present. Note again that edges do not cross; thus there are many phantom triangles in the above diagram, but only the triangles that connect three vertices are relevant to our purpose. Conversely, just as K₅ is not required to be drawn with straight-line edges, K₃ may be drawn with non-straight edges, so triangles may not even look like triangles! If it helps, instead of ‘triangle’, you can think ‘K₃‘. Yeah, I didn’t think that would help.

So let us consider that the vertices represent people at a reception (yes, I know, 5 people is a very small reception), and the edges represent the relationships between every pair of people. Now receptions usually have food, and food requires tables, and eating at tables implies dinner conversation. Now every good host knows that you can’t allow for tables full of complete strangers (how awkward!) or complete friends (how cliquish!). Since ‘friend’ and ‘stranger’ are properties of a pair of people, we can illustrate these properties in our graph by assigning colors to the edges of the graph. We’ll say red for strangers, blue for friends. Every edge gets a color.

Well this reception is in a hall that only has tables that seat three, and the host has no control over which guests sit together — maybe he’s lazy, or I don’t know, maybe he instituted a seat lottery — the point is, the host is concerned about the possibility of 3 of our 5 guests ending up at a lame table together, and being scarred for life due to the awful conversation, and undoubtedly suing the host for millions (but not so concerned that he is willing to resort to assigned seating — we all know what a political minefield that can be)! The way our host has chosen to escape the horns of his seating dilemma is not by controlling the seating, but by controlling the guest list, so that there is no possibility of a bad seating.

So the question is: is it possible to have a 5-person party, such that

• there are not three people who are all friends, and
• there are not three people who are all strangers?

The equivalent question in graph theory goes like this:

Is it possible to 2-color the edges of K₅ such that there are no monochromatic K₃?

This puzzle is pretty easy, so give it a try, and I’ll give you harder ones later (stick with me; I’m building up to something cool). Draw (or print) the graph, find some crayons (or dry-erase markers) and experiment a little. Alternatively, you could consider the two colors ‘black’, and ‘invisible’. Start with 5 unconnected vertices (or are they all connected with edges of color ‘invisible’?), and color edges black until you have no all-black triangles, and no all-invisible triangles.

[Go find the answer, and another puzzle, here]