5 ms·
I'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 identic
by sharpneli 16y ago
I'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.