Forbidden subgraphs of graphs uniquely Hamiltonian-connected from a vertex

AbstractA graph G is called uniquely Hamiltonian-connected from a vertex v if, for every vertex u ≠ v, there is exactly one v − u Hamiltonian path in G. We show that if G is uniquely Hamiltonian-connected from v and H is a subgraph of G − v then |E(H)| ⩽ (3|V(H)| − 2)/2. The bound on the number of edges is best possible in that there exists graphs H with exactly ⌊(3|V(H)| − 2)/2⌋ edges which are forbidden and others which can occur as subgraphs