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.