Define a "Hamilton-connected graph $G$" as
For any vertices $u, v \in G$, a Hamilton path exists, where the two ends of the path are vertices $u$ and $v$. Try to prove that if $G$ is a Hamilton-connected graph and $|V(G)| \geqslant 4$, the following inequation holds:
$$|E(G)| \geqslant [\frac12(3|V(G)|+1)]$$
Note 1: $[x]$ is "round down" or Math.floor().
Note 2: Per my textbook, a Hamilton path is not a cycle (i.e., $(u,v)\in E(G)$ is not necessarily true).
After some attempts, I think the question is wrong and the inequation I can work out is
$$|E(G)| \geqslant [\frac32|V(G)|]$$
because I've found out that it's possible to have graphs that meets the requirement with $(|V|,|E|)=(4,6)$ and $(5,7)$, both of which violates the inequation in the question, while matching my refined one.
Kindly tell me whether my refined inequation is correct and how to prove it.
Disclosure: This is a question from my homework of a graph theory course.
Best Answer
I want to first note that a graph with $(|V|,|E|)=(4,6)$ does not disprove the inequality, since each side evaluates to $6$. Your example with $(|V|,|E|)=(5,7)$ cannot exist, due to the following proof.
Note that $$ |E(G)| \geqslant [\frac12(3|V(G)|+1)]\iff \begin{array}{} |E(G)| \geqslant \frac12(3|V(G)|+1)& \text{for odd }|V|\\ |E(G)| \geqslant \frac12(3|V(G)|) & \text{for even }|V| \end{array}$$ Since $2|E(G)|=\sum_{v\in V}deg(v)$, $$ \begin{array}{} \sum_{v\in V}deg(v) \geqslant 3|V(G)|+1& \text{for odd }|V|\\ \sum_{v\in V}deg(v) \geqslant 3|V(G)| & \text{for even }|V| \end{array} $$ We will show that every vertex in a Hamiltonian connected graph must have at least degree $3$. Suppose (for the purpose of contradiction) that $G=(V,E)$ is Hamiltonian connected with $|V|\ge 4$ and that $v\in V$ has degree $2$. Say that $v$ has exactly neighbors $x,y$. Consider a Hamiltonian path from $x$ to $y$. Since $v$ has only two neighbors, then the first vertex in this Hamiltonian path must be $v$, or else $v$ will be unreachable before reaching $y$. However, if the vertex $v$ is second on the Hamiltonian path, then the only possible vertex to be third is $y$. But there must be at least $4$ vertices so this is not a Hamiltonian path. This is a contradiction, so the vertices of every Hamiltonian connected graph with $|V|\ge 4$ must have degree at least $3$.
For even $|V|$, since each vertex has degree at least $3$, $$ \sum_{v\in V}deg(v) \geqslant 3|V(G)| $$ For odd $|V|$, since each vertex has degree at least $3$ and since the sum of all of the degrees cannot be odd, then $$ \sum_{v\in V}deg(v) \geqslant 3|V(G)|+1 $$