Hamilton-connected graphs have a chromatic number at least 3 A Hamilton-connected graph is a graph where for every pair of vertices there exists a hamiltonian path that connects them.
I'm trying to prove that the chromatic number of a Hamilton-connected graph $G$ is always greater or equal than 3 ($\chi(G) \ge 3$).
 A: Note that if $G$ is the graph $K_2$ (consisting of a single edge), then the chromatic number of $G$ is 2 and yet $G$ has a hamilton path between any two vertices.  So we need to assume $G$ has at least 3 vertices.
Let $G$ be a hamilton-connected graph on 3 or more vertices. We want to show $\chi(G) \ge 3$.  By way of contradiction, suppose $G$ has a 2-coloring.  So $G$ is bipartite, with bipartition $(V_1,V_2)$ say. Here, at least one part has 2 or more vertices, say $|V_1| \ge 2$.   Observe that if we pick two vertices $x,y \in V_1$, then there is a hamilton path from $x$ to $y$. This path has both its endpoints in $V_1$, which implies that $|V_1| = |V_2|+1$.  If $x \in V_1$ and $y \in V_2$, then there is a hamilton path from $x$ to $y$, which implies $|V_1|=|V_2|$, a contradiction.
A: As i was writing down the question i came up with the following solution (not sure if 100% correct, so any input is welcome):  
It is sufficient to prove that there doesn't exist a 2-coloring of $G$.  
For a 2-coloring to exist in G, the Hamilton path connecting each pair of vertices with the same color must contain an odd number of vertices (and vice versa).
So, if we say that the graph has $V(G)=2k$ vertices, and choose 2 random vertices $u,v$,the path connecting them will have an even number of vertices, so $\chi(u)=\chi(v)=1$, if we pick a random vertice $x$ with $\chi(x)=2$, then there must exist a Hamilton path connecting $x,u$ containing even vertices, which cannot be colored with only 2 colors.
