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)$?


1 Answer 1


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.