How to understand if task on graph-theory has analytical solution?

Several Top Secret Objects are connected by an underground railway in such a way that each Object is directly connected to no more than k = 3 others, and from each Object you can get underground to any other with no more than one change. What is the maximum number of Top Secret Objects?

Solution for the task

So 10 nodes. But is there analytical solution?
I have idea: from one node can come to k others, and from each out of this k else to k others. Thus, number of nodes $= k^2 + 1$. Maybe it's good idea, but I can't prove it for $k\geq2$...

Solution 1:

Say we $n$ objects and we have $e$ connected pairs and $e'$ unconnected pairs of objects.

• Then by the Handshake lemma we have $e\leq {3n\over 2}$.

• Now make bipartite graph $H=(P,O)$ where $P$ consist of unconnected pairs of objects and $O$ are simply objects. In $H$ we connect a pair $\{u,v\}\in P$ with object $o\in O$ iff $o$ is connected with both $u$ and $v$.

  Since there we can get fro any $u$ to $v$ with exactly one change we see that each pair $\{u,v\}$ has degree $1$ and since every $o$ is connceted to at most 3 other objects it is connected with at most ${3\choose 2}=3$ pairs in $P$. Since $|P| =e'$ and $|O|=n$ we have $e'\leq {3\choose 2}\cdot n =3n$.

Now we have $${n\choose 2} = e+e'\leq {3n\over 2} +3n$$ and thus $$n-1\leq 3+6\implies n\leq 10$$

In general equality case is possible if $$n =k^2+1$$