5 ms·
"the world is a sphere, and friends don't cross each other." My guess would be that the social graph needs to be planar (e.g embeddable on a plane so that no e
by sharpneli 16y ago
"the world is a sphere,
and friends don't cross each other."
My guess would be that the social graph needs to be planar (e.g embeddable on a plane so that no edges go across eachother).
The world is a sphere can be interpreted in too many ways. One would be that there exists a hamiltonian cycle for the graph and other would be that if you do a depth first search you'd always hit yourself eventually.
My strong guess would be that 2 friends is the least and the most a loser may have.
Biggest problem with too smart puzzles such as this is that there are way too many ways to legitimately interpret them.
- jaekwon 16y agoThe social graph need not be planar, say if the world is a donut.
- sharpneli 16y agoI'd consider that a minor adjustment as it would still essentially be a planar graph (with periodic boundary conditions). Locally both of the cases look identical. Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
- jaekwon 16y agoI'm sorry, the puzzle is asking for a global property. The new text has the adjustments.
- sharpneli 16y agoI think I got it now. Don't read this if you are afraid of possible spoiling. We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less neighbours and therefore lowering the smallest edge count.
- lisper 16y agoI don't think it's possible to tile a sphere with hexagons. You have to throw a couple of pentagons in. http://en.wikipedia.org/wiki/Geodesic_dome http://en.wikipedia.org/wiki/Geodesic_dome
- sharpneli 16y agoTrue. So for a spherical topology the largest minimum is 5. However for toroidal topology the largest minimum is 6.