# Prove that every two vertices in graph are connected by a path of some length

I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning.

Every node in network is connected to exactly 3 others. Is it possible for me to prove that every two nodes have a path of length O(n/3) between them? I can show people that the way I setup the network guarantees some existence of relatively fast routes. The n is much more than 3

Thank you

$O(n/3)$ doesn't mean what you think it means: in particular, $O(n/3)$ denotes exactly the same class of functions as $O(n)$. However, it's not true that the longest distance between two vertices in a $3$-regular graph is roughly $n/3$. Consider the graph

o---o       o       o             o       o---o
|\ / \     /|\     /|\           /|\     / \ /|
| X   o---o | o---o | o-- ... --o | o---o   X |
|/ \ /     \|/     \|/           \|/     \ / \|
o---o       o       o             o       o---o


(where the Xs denote two crossing edges). The distance from the top-left vertex to the top-right vertex is approximately $3n/4$.

• Thank you for picture, it's very informative. I see the error of the questioning now. Does same reasoning still hold if 3 is 3 billion? If it's many many magnitudes greater than n?
– ojil
Mar 27 '17 at 0:25
• $n$ is usually the number of vertices in the graph. Do you mean something else by it? Because, if there are $n$ vertices, no vertex can have more than $n-1$ neighbours, and it certainly can't have a number of neighbours that's "many magnitudes greater." I'm not sure what the answer is for values between $3$ and $n-1$. Try Googling for something like "diameter of bounded degree graphs". (If I remember, I'll have a look in the morning but I need to go to bed, now.) Mar 27 '17 at 0:30
• Thank you for the help and resources, error in the phrasing. I meant to inquire for n is 3 billion and is the many many magnitudes greater than 3 edges between all nodes. I will Google.
– ojil
Mar 27 '17 at 0:40