Given several cities in a country. City X is directly connected to 23 other cities. City Y is directly connected to 3 other cities. Each city, except X and Y, is directly connected to 10 other cities. Prove that there is an route (maybe with city changes) between X and Y.
I used handshaking lemma in this case and got the number of edges according to the constraints which can then be compared with the minimum number of edges needed in graph so that it is connected.
Here the number of vertices can be at the most 28 according to the constraints.
Is there a better approach to prove the same?
This is a rather simple problem if you do this trick:
Suppose our graph is $G$. We assume there is no path between $X$ and $Y$. Thus, $G$ is not connected.
Let us split $G$ into $G_1$, $G_2$,...,$G_k$, all disjoint and connected. There is no edge between $X$ and $Y$ means that $X$ and $Y$ are not in the same $G_i$.
Let $n$ such that $X\in G_n$. Then, suppose we have $x$ other cities, which are different from $Y$, so they all have a degree of $10$. The degree of $X$ is $23$, so $$\sum_{v\in G_n}deg(v)$$
is odd, which is a contradiction, because in any graph $$\sum_{v\in G}deg(v)=2e$$
where $e$ is the number of edges.
So there must be a path between $X$ and $Y$
Note: this problem can be generalized in many ways. The only important values here are the parity of degrees. Good luck!