Is this graph a hamiltonian graph?

Question

I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, iteratively. Every node added onto the graph and has 2 connections with the existing nodes (not necessarily with the initial 3 only) in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.

I'm asked, what is the maximum number of nodes in this graph that can be visited exactly once (except for the initial node), i.e., what is the maximum number of nodes contained in the largest Hamiltonian path of the given graph. (Okay, saying largest Hamiltonian path is not a valid phrase, but considering the question's nature, I need to find a max. number of nodes that are visited once and the trip ends at the initial node. I thought it can be considered as a sub-graph which is Hamiltonian, and consists max. number of nodes, thus largest possible Hamiltonian path).

I tried to apply Ore's Theorem but even for a small example graph, the Ore's Theorem might not be sufficient to tell if the graph is Hamiltonian even though it strikes you directly that it is Hamiltonian.

I thought I might use BFS since It's used to detect cycles in a graph: I needed to find the largest cycle which contained all the nodes in that cycle but given a large number of nodes, this approach might be slow and not desirable in my case since the timing will be crucial. For now this option is the last option if I can't come up with a solution.

After some thinking, I thought whatever the number of nodes will be, the graph seems to be Hamiltonian due to node addition criteria. The problem is I can't be sure and I can't prove it. Does adding nodes in that fashion, i.e. adding new nodes with 2 edges which connect the added node to the existing nodes, alter the Hamiltonian property of the graph? If it doesn't alter the Hamiltonian property, how so? If it does alter, again, how so? Thanks.

EDIT

I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:

1 3
2 3
1 5
1 3

these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .

4th and 7th node are connected to the same nodes, thus lowering the maximum number of nodes that can be visited exactly once, by 1. If i detect these collisions (including an input such as 3 3) and lower the maximum number of nodes, starting from N, I believe I can get the right result.

See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.

I think counting the same connections while building the graph and subtracting it from N will give the right result? Can you confirm this or is there a flaw with this?

Answer 1

Let $k_P$ and $k_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=(1,2,3,4)$ and $P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.