so I'm trying to complete this question for uni and am stuck.
show that G = (V, E) has no Hamiltonian cycle, where the vertices are V = {a, b, c, d, e, f, g} and the edges are E = {ab, ac, ad, bc, cd, de, dg, df, ef, fg}
i was wondering if there was a simple way to solve this. thank you :)
HINT: Vertex $d$ is the key. Let $U=\{a,b,c\}$ and $W=\{e,f,g\}$. Every path between a vertex in $U$ and a vertex in $W$ passes through $d$. Use this observation to show that any circuit that visits every vertex must pass through $d$ at least twice. Since a Hamilton cycle is a circuit — it returns to its starting point — you may use any vertex as the starting and ending vertex; to avoid minor complications, pick one that isn’t $d$.