Prove that $G$ is Hamiltonian.

Question

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ then G is Hamiltonian.

My proof:

I will show that every vertex $w \in V$ is part of some cycle. Proof by contradiction. Let's assume that there exsists a vertex $v$ which is not a part of any cycle. Let's take now any cycle C.

Let $V(C)=v_1,v_2,...,v_k$

Of course $v\in V(G) - V(C)$

$V(C)$ has to have at least 3 vertices (by the definiton of a cycle), so $v$ is connected to at least 2 vertices in C, let them be $v_1,v_2$.

Now if $v_1$ and $v_2$ are connected then $v,v_1,v_2$ is a cycle - contradiction. If $v_1$ and $v_2$ are not connected, then $v,v_2,...,v_k,v_1,v$ is a cycle - contradiction.

That proves that indeed every $v\in V(G)$ is a part of some cycle.

If graph is made only of cycles, then it has a Hamiltionian cycle Q.E.D.

Answer 1

You are close to prove Hamiltonicity of such graphs. Just use for example induction to show that if there exists cycle $C$ of length $|C|$ in graph $G$ then there exists a simple cycle $C_k$ of length $k$ for any $k$ between $|C|$ and $|G|$, inclusive.

Answer 2

Since the graph is not a tree, it has at least a cycle.

Pick a cycle $C$ with the most number of vertices. I claim, it is a Hamiltonian cycle.

Indeed, assume by contradiction is not Hamiltonian. Let $v$ be a vertex outside the cycle. Use the pigeonhole principle, and the given condition to show that $v$ is connected to two consecutive vertices on the cycle.

Show that this implies that $v$ can be added to the cycle, contradicting the maximality of $C$.