\(\Im\)
Imagine that you are invited to a party, and there is a special rule: due to the host's intention to facilitate socialization and enliven the event, every pair of previously unacquainted persons must sing karaoke together for 2 minutes. However, you also have an appointment 2 hours after the party starts. You know there are 15 people at the party, and because the host also doesn't want to spend so much time listening to potentially some unrefined voices, he/she assures you that for any group of 4 people, there is at least one pair of acquaintance. Now, would you be able to listen to all karaoke performances before you leave for the appointment(assuming as soon as one karaoke performance ends, the next one starts, and this lasts for the whole party)?
Or, suppose you are the host of a party, and now you have to distribute your guests to different(possibly one) table(s). Each table is round and large, and once seated, every person is supposedly surrounded by two other people. Before the party, you were given the lists of friends of all the guests. So, do you know whether it's possible to allocate everyone to a table such that each of them has two friends surrounding him/her?
If you are tired of parties, how about the following: in Königsberg(now known as Kaliningrad in Russia), there were seven bridges connecting some lands and islands, shown as the following:
So is it possible to start somewhere in this map and walk around, using every bridge once, and eventually return to the starting location without repeating any bridge(no pun intended)? More interestingly, the configuration of the bridges nowadays is different from before due to the bombing of Königsberg in World War II:
The red marks indicate the destroyed bridges, and the green ones are the preserved ones. How about now?
\(\Im\)
In fact, all of these questions can be answered with a major branch in combinatorics, namely graph theory. Let's explore it from the very basic level and appreciate its ubiquitous wonder.
start exploring...