Draw all connected graphs of order $5$ in which the distance between every two distinct vertices is odd. Explain why you know that you have drawn all such graphs.
Let $P = (u = v_0, v_1, \ldots, v_k = v)$ be a $u − v$ geodesic in a connected graph $G$. Prove that $d(u, v_i) = i$ for each integer $i$ with $1 \le i \le k$.
My attempts at solutions:
-
A graph of order $5$ has $5$ vertices, so the distance between every two distinct vertices has to be $1$ or $3$ or $5$. Every two vertices include adjacent ones as well. Adjacent vertices are connected with only one edge. That means we can draw only one connected graph with $5$ vertices.
-
Let $P$ be a $u – v $ geodesic in a connected graph $G$. Then the distance between $u$ and $v$ is the smallest length of any $u − v$ path in $G$ by definition. Hence $d(u, v_k) = k$ and no $u − v$ path of smaller length exists in $G$ . But by assumption $i$ is an integer with $1 \le i \le k$, so $d(u, v_i) = i$.
Are these correct?
Best Answer
As for 1), it seems you got the right idea but what does "Every two vertices include adjacent ones as well." mean ?
My personal way of saying it would be : if you have two vertices $u, v$ at distance 3 or 5, then necessarily there's a vertex at distance 2 from $u$ on the shortest $u - v$ path (That's what point 2. says !). So the only available odd distance is actually 1, which leaves only one possibility.
For 2), you might want to complete the proof by stating why you can't have $d(u, v_i) < i$, nor $d(u, v_i) > i$ for any $1 \leq i < k$. That is, $d(u, v_k) = k$ by definition, but what about the other values of $i$.