title: How to detect if the given graph has a cycle containing all of its nodes? Does the suggested algorithm have any flaws?
body: <p>I have a connected, non-directed, 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. Every node added onto the graph and has 2 connections with the existing nodes in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.</p>
  
  <p>Originally 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? <em>(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).</em></p>
  
  <p>Since i'm not asked to find a path, I should check if a hamiltonian path exists for given number of nodes first. I know that planar graphs and <a href="http://en.wikipedia.org/wiki/Cycle_graph" rel="nofollow">cycle graph</a>s (C<sub>n</sub>) are hamiltonian graphs (I also know <a href="http://en.wikipedia.org/wiki/Ore%27s_theorem" rel="nofollow">Ore's theorem</a> for Hamiltonian graphs, but the graph I will be working on will not be a dense graph with a great probability, thus making Ore's theorem pretty much useless in my case). Therefore I need to find an algorithm for checking if the graph is cycle graph, i.e. does there exist a cycle which contains all the nodes of the given graph. </p>
  
  <p>Since DFS is used for detecting cycles, I thought some minor manipulation to the DFS can help me detect what I am looking for, as in keeping track of explored nodes, and finally checking if the last node visited has a connection to the initial node. Unfortunately
  I could not succeed with that approach.</p>
  
  <p>Another approach I tried was excluding a node, and then try to reach to its adjacent node starting from its other adjacent node. That algorithm may not give correct results according to the chosen adjacent nodes.</p>
  
  <p>I'm pretty much stuck here. Can you help me think of another algorithm to tell me if the graph is a cycle graph?   </p>
  
  <p><strong>Edit</strong></p>
  
  <p>I realized by the help of the comment (thank you for it n.m.): </p>
  
  <blockquote>
    <p>A cycle graph consists of a single cycle and has N edges and N vertices. If there exist a cycle which contains all the nodes of the given graph, that's a Hamiltonian cycle. – n.m.</p>
  </blockquote>
  
  <p>that I am <em>actually</em> searching for a Hamiltonian path, which I did not intend to do so:)
  On a second thought, I think checking the Hamiltonian property of the graph while building it will be more efficient, which is I'm also looking for: time efficiency. </p>
  
  <p>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.</p>
  
  <p><strong>EDIT #2</strong></p>
  
  <p>I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:</p>
  
  <pre><code>1 3
  2 3
  1 5
  1 3
  </code></pre>
  
  <p>these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .</p>
  
  <p>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 (<strong>NOT</strong> including an input such as 3 3, which is an example that you suggested since the problem states that the newly added edges are connected to <strong>2 other nodes</strong>) and lower the maximum number of nodes, starting from N, I believe I can get the right result.</p>
  
  <p>See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.</p>
  
  <p>I think counting the same connections while building the graph and subtracting the number of same connections from N will give the right result? Can you confirm this or is there a flaw with this algorithm?</p>