5
$\begingroup$

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It's essential to show the upper and lower bounds for this question.

Now, I can see why I need to show the upper bound - for $t(n,H_n) > \binom{n-1}{2} + 1$ there's a clique on $n-1$ vertices and one other vertex with at least 2 edges. Surely, a Hamiltonian cycle exist in such graph.

What about the lower bound, though? Am I need to prove that for every $t(n,H_n) \leq \binom{n-1}{2} + 1$ there is no Hamiltonian cycle? By negation, I seem to not advance anywhere, because I don't know of any necessary conditions for a Hamiltonian cycle to exist, beside the cut-vertex one. Can someone give me a clue on that?

Thanks in advance.

  • 0
    How do you justify your claim that "for $t(n,H_n)\gt\binom{n-1}2+1$ there's a clique on $n-1$ vertices"? This doesn't seem right to me. Suppose $n=5.$ then $\binom{n-1}2+1=7 ,$ but I can draw a graph with $5$ vertices and $8$ edges which does not contain a clique on $4$ vertices. Namely, take the complete graph $K_5$ and remove two independent edges.2017-08-28

4 Answers 4

13

Found a lot easier proof for the harder part, using Ore's theorem: If $G$ is complete, there's a Hamiltonian cycle. So suppose it's not. We'll take some non-neighbor vertices $v,w$, and delete them from the graph. For the resulting graph G' - |E(G')| \geq \binom {n-1}{2} + 2 - (d(v)+d(w)). In the complete graph on $n-2$ vertices there are $\binom {n-2}{2}$ edges. So, lastly, we get that $\binom{n-2}{2} \geq \binom{n-1}{2} + 2 - (d(v)+d(w))$ and after some easy operations, we get that $d(v)+d(w) \geq n$ which is exactly Ore's condition for a Hamiltonian graph to exist.

5

A different induction solution:

Induction hypotheses: A (simple) graph G with $\binom {n-1} 2 +2 $ edges has a hamiltonian cycle.

For $n=2$ and $n=3$, we can prove the claim by exhausting all possibilities(where $n$ is the number of vertices).

For $n>3$: There is a vertex with degree atleast $n-2$. This is true because there are $\dfrac{(n-1)(n-2)}2+2$ edges, hence sum of degree of all the vertices is $(n-1)(n-2)+4=n^2-3n+6$. Suppose, all vertices had degree $n-3$ or less, then it would make upto a maximum of $n(n-3)$.

Case $1$: There is a vertex of degree $n-1$

Removing this vertex creates a $n-1$ vertex graph with $\dfrac{(n^2-5n+8)} 2$ edges, whereas we need $\dfrac {(n-2)(n-3)}2+2=\dfrac{(n^2-5n+10)}2$ for a hamiltonian cycle. But it is enough for a hamiltonian path to exist (from induction). Since, the removed vertex has degree $n-1$, the hamiltonian path in the smaller graph can be converted into a hamiltonian cycle in the bigger graph.

Case $2$: There is a vertex with $n-2$ and no vertex with degree $n-1$.

Removal of this vertex creates a graph with $\dfrac{(n^2-3n+2)}2-(n-2)+2=\dfrac{(n-2)(n-3)}2 +2$. By induction, the smaller graph contains a hamiltonian cycle. Since, the removed vertex has degree $n-2$, we can find two adjacent vertices in the hamiltonian cycle and insert the vertex there.(this is why we required the induction base case for $n=3$) $\blacksquare$

Example of a(is it the only?) graph with $\binom {n-1} 2+1$ edges and not hamiltonian: Union of $K_{n-1}$ and a vertex outside that shares an edge with exactly one vertex of $K_{n-1}$ .

  • 0
    I make no remark about the correctness of the answers. As for formatting, click on the time stamp above my name to access the edits. Welcome to MSE. I have upvoted your answer.2012-03-23
3

This is essentially Corollary 4.6 in the book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. I wonder if there is an easy proof for this statement. Maybe there is one but I don't know it. Since you said that this is a homework problem, I think you may be able to apply some theorem you have learned in your class. If you have learned Chvatal's theorem in your class (see Theorem 4.6 of the book mentioned above), which says that:

If $G$ is a non-Hamiltonian simple graph with $n\geq 3$ vertices, then $G$ is degree-majorised by some $C_{m,n}:=K_m\vee(K_m^c+K_{n-2m})$

then you can derive the required result easily as follows, as shown in the book: $|E(G)|\leq |E(C_{m,n})|=\frac{1}{2}\Big[m^2+(n-2m)(n-m-1)+m(n-1)\Big]\leq{n-1\choose 2}+1.$ On the other hand, you can characterize $G$ when the equality holds.

  • 0
    The link doesn't work.2018-12-04
-1

First see that you can have a complete graph on n-1 vertices where the number of edges is n-1 C 2 and then you just need to consider how many edges you can add to a new incoming vertex such that the resulting graph is Non- Hamiltonian. Hamiltonicity of the complete graph implies that only one edge can be added .