And, as with every polyhedral graph, its planar embedding is unique up to the choice of which of its faces is to be the outer face. Every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex. Because every tree without vertices of degree 2 contains two leaves that share the same parent, every Halin graph contains a triangle. In particular, it is not possible for a Halin graph to be a triangle-free graph nor a bipartite graph. More strongly, every Halin graph is almost pancyclic, in the sense that it has cycles of all lengths from 3 to "n" with the possible exception of a single even length. Moreover, any Halin graph remains almost pancyclic if a single edge is contracted, and every Halin graph without interior vertices of degree three is pancyclic. The incidence chromatic number of a Halin graph with maximum degree greater than four is . This is the number of colors needed to color all pairs ("v","e") where "v" is a vertex of the graph, and "e" is an edge incident to "v", obeying certain constraints on the coloring. Pairs that share a vertex or that share an edge are not allowed to have the same color. In addition, a pair ("v","e") cannot have the same color as another pair that uses the other endpoint of "e". For Halin graphs with or , the incidence chromatic number may be as large as or respectively. It is possible to test whether a given -vertex graph is a Halin graph in linear time, by finding a planar embedding of the graph (if one exists), and then testing whether there exists a face that has at least vertices, all of degree three. If so, there can be at most four such faces, and it is possible to check in linear time for each of them whether the rest of the graph forms a tree with the vertices of this face as its leaves. On the other hand, if no such face exists, then the graph is not Halin. Alternatively, a graph with vertices and edges is Halin if and only if it is planar, 3-connected, and has a face whose number of vertices equals the circuit rank of the graph, all of which can be checked in linear time. Other methods for recognizing Halin graphs in linear time include the application of Courcelle's theorem, or a method based on graph rewriting, neither of which rely on knowing the planar embedding of the graph.