Let $G = (V, E)$ be a finite, simple, undirected graph with $V \cap E = \emptyset$. The *total graph* $T(G)$ is defined on the vertex set $V \cup E$ and its edge set is given by $$E(T(G)) = E \cup \big\{\{e, f\}: e, f \in E\text{ and } |e\cap f| = 1\big\}\cup \big\{\{v, e\}: v\in V, e\in E, v\in e\big\}.$$


**Question.** If there is a Hamiltonian path in $G$, is there a Hamiltonian path in $T(G)$?



Hamiltonian path in total graph
The edges incident to $v \in V$ form a clique in $T(G)$, so the Hamiltonian path $v\_1, v\_2, v\_3, \ldots, v\_n$ in $G$ can be lifted into a Hamiltonian path in $T(G)$ as follows:


1. Insert the edges to get $v\_1, \{v\_1, v\_2\}, v\_2, \{v\_2, v\_3\}, v\_3, \ldots, v\_n$.
2. In arbitrary order, insert every edge which is not already included in the path immediately after one of its vertices.


