This is a **graph**. The nickname of this graph is K_{5}, 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_{5}, 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_{5} in a plane without crossed edges, the universe would certainly implode!).

Note that K_{5} contains many **triangles** (or K_{3}, in graph theory parlance). The reason K_{5} 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_{5} is not required to be drawn with straight-line edges, K_{3} 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_{3}‘. 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

_{5}such that there are no monochromatic K_{3}?

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]

Bruce, on September 21, 2006 at 2:18 pm said:black={1,2}, {1,5}, {2,4}, {3,4}, {3,5}

red= {1,3}, {1,4}, {2,3}, {2,5}, {4,5}

RubeRad, on September 21, 2006 at 2:51 pm said:We have an early winner! And in an abstruse-enough edge-listing format that anybody else that attempts will not necessarily comprehend the answer.

I’ll note that, while correct, there is a sense in which that is not the ‘easiest-possible’ answer, where ‘easiest-possible’ means describable just with concise English. I can name that tune in, ummm, four words…

Bruce, on September 21, 2006 at 3:12 pm said:Does that mean that, while I got the right answer, I don’t win the free BMW on some technicality?

RubeRad, on September 21, 2006 at 6:16 pm said:Look at you! You

aresmart, aren’t you!?Puzzle II « Blogorrhea, on September 23, 2006 at 6:31 pm said:[…] Comment on Pope v. Islam by the foresterComment on Pope v. Islam by the foresterComment on Pope v. Islam by Aunt BarbaraComment on Moses’ Law is not God’s Law by AnonymousComment on Puzzle I by RubeRadComment on Puzzle I by BruceComment on Puzzle I by RubeRadComment on Puzzle I by BruceComment on Pope v. Islam by Aunt BarbaraComment on Pope v. Islam by RubeRad […]

Puzzle III.2: Combinations « Blogorrhea, on October 13, 2006 at 5:14 am said:[…] Puzzle I […]

Puzzle III.3: Big Numbers « Blogorrhea, on October 15, 2006 at 4:39 pm said:[…] Puzzle I […]

Puzzle III.4: Epilogue « Blogorrhea, on October 18, 2006 at 9:17 am said:[…] Comment on Puzzle III.3: Final Answer by RubeRadComment on Puzzle III.3: Final Answer by the foresterComment on Puzzle III.3: Final Answer by RubeRadComment on Obedience is better than… by the foresterComment on Puzzle III.3: Final Answer by the foresterComment on Sacra-licious by Mike SComment on Sacra-licious by RubeRadComment on Sacra-licious by Albino HayfordComment on Puzzle III.3: Final Answer by Puzzle III.2: Combinations « BlogorrheaComment on Puzzle I by Puzzle III.3: Big Numbers « Blogorrhea […]

TAG, you’re it « Blogorrhea, on October 22, 2006 at 1:20 pm said:[…] Comment on Obedience is better than… by limejellyComment on Sacra-licious by Mike SComment on Puzzle I by Puzzle III.4: Epilogue « BlogorrheaComment on Puzzle III.3: Final Answer by Puzzle III.4: Epilogue « BlogorrheaComment on Puzzle III.3: Final Answer by RubeRadComment on Puzzle III.3: Final Answer by the foresterComment on Puzzle III.3: Final Answer by RubeRadComment on Obedience is better than… by the foresterComment on Puzzle III.3: Final Answer by the foresterComment on Sacra-licious by Mike S […]