Is it possible to make a graph consisting of 2n nodes such that every node is connected to every other node in at least n steps except n of the other nodes? For example with 1, we make the graph with adjacency matrix $\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}$. I couldn't make larger ones, I tried 2,3,4 with code and didn't find anything but cannot prove it is impossible for larger integers. This question was found by expanding on another math problem.
4
-
$\begingroup$ Have you tried other small examples? What happens for $n=2$? $\endgroup$jjagmath– jjagmath2025-11-24 11:23:14 +00:00Commented Nov 24 at 11:23
-
$\begingroup$ I could not find n=2 by hand in what little time I had during the math class where a friend asked me this. $\endgroup$paajny657– paajny6572025-11-24 11:32:11 +00:00Commented Nov 24 at 11:32
-
$\begingroup$ In this forum you're expected to show some effort in order to get help. Edit your question to include your work on the problem, otherwise your question will be downvoted and eventually closed. $\endgroup$jjagmath– jjagmath2025-11-24 11:53:12 +00:00Commented Nov 24 at 11:53
-
$\begingroup$ May be I'm not understanding your question, but the square seems to satisfy the condition you're describing. $\endgroup$jjagmath– jjagmath2025-11-24 13:32:57 +00:00Commented Nov 24 at 13:32
Add a comment
|