2 added 26 characters in body edited Apr 7 '13 at 14:12 Raphael♦ 58.9k2525 gold badges144144 silver badges327327 bronze badges 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=1234$$$$C=(1,2,3,4)$$ and $$P=21435$$$$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. Let $$k_P$$ and $$k_C$$ be the maximum length of a 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=1234$$ and $$P=21435$$ 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. 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. 1 answered Apr 7 '13 at 13:37 fidbc 26611 silver badge33 bronze badges Let $$k_P$$ and $$k_C$$ be the maximum length of a 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=1234$$ and $$P=21435$$ 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.