1

In a try to generalize this problem I came up with the following question: Is there any number $N$ such that for given $N$ points in space it is possible to join all of them with paths (each path connects two different points) such that:

Every point is connected by at least 4 paths (i.e., degree of each vertex is bigger than 3) and

for every point the smallest closed loop (i.e., going back to itself) following the paths goes through at least 3 other points and

for any two points there is a series of paths connecting them?

Community
  • 1
Rol
  • 613

1 Answers1

1

Yes. An example is afforded by the hypercube graph $Q_4$ on $N=16$ vertices. The Wikipedia article on hypercube graphs has an illustration of $Q_4$ that makes it easy to check this.

joriki
  • 238,052