FYI if four of them have the same surname it's obvious that all 4 have a common ancestor somewhere down the line.
That's not necessarily true. It depends on which town your ancestors came from. Surnames in ancient days were made up randomly as fancied after the idea of family and clan names caught on. Later on, it was used to prevent accidental incest. It was common that a village or small town be given two or three or a few surnames only. Within the village or town, they must marry one of the other surnames. However, other villages and towns may be given some of the same surnames too. They had no blood relation. As villages grew into towns and towns grew into cities, some surnames would inadvertently grew disproportionately in population. That's why in traditional Chinese introduction, the surname and the town they came from is given first, e.g. "I'm surnamed Lim from Hokkien Anhui." In clan associations, if you visit one and read the signboard properly, the originating town is also written.
The traditional Chinese naming and identification system was also more complex than you think and even most modern Chinese don't know. After the surname and town of origin identificaton, there were a given name at birth (ming) and a taken name (zi) at adulthood. Addressing each other by taken name meant casual friends or acquaintences in formalities. Addressing each other by given name meant relatives or close friends.
The Mongolians and Manchurians who at one time or another ruled China, didn't abolish that system. It was ROC that abolished that system, or as they said, modernized and simplified the system.