0
$\begingroup$

if a graph has only 3 vertices, can it have a Hamilton cycle. I know it has a Euler cycle because you can hit every edge at least once without doubling. If a graph only has 3 vertices though can you visit every vertex once?

$\endgroup$

1 Answer 1

1
$\begingroup$

It depends on the graph. There are only four distinct graphs with $3$ nodes. We can look at each of them. Let's label our three nodes as $1$, $2$, and $3$ and represent each graph as a set of its edges: $$ \begin{align} G_1 &= \{\} \\ G_2 &= \{(1,2)\} \\ G_3 &= \{(1,2), (2,3)\} \\ G_4 &= \{(1,2), (2,3), (1,3)\} \\ \end{align} $$

Note that $G_1$, $G_2$, and $G_3$ do not have Hamilton cycles, but that $G_4$ does.

$\endgroup$
5
  • 1
    $\begingroup$ @MD_90 ..and that only $G_4$ is Eulerian. $\endgroup$
    – Casteels
    Commented Feb 8, 2015 at 7:14
  • $\begingroup$ @Casteels, right. I forgot that a Hamilton cycle needed to be a cycle. My answer has been edited. $\endgroup$ Commented Feb 8, 2015 at 7:16
  • $\begingroup$ What's the best way to find Euler paths, circuits and same ideas for Hamilton paths and circuits. I'm still new to discrete mathematics so understanding these topics is a struggle so far. Is any good techniques for approaching graphs to find isomorphism, bipartite, Euler circuits and paths, and Hamilton paths and circuits. I do know the formula of n(n-1)/2 for complete graphs but im still not sure of if its uses. Please give me any methods that will help make this subject better to understand. $\endgroup$
    – MD_90
    Commented Feb 8, 2015 at 7:18
  • $\begingroup$ Also what does it mean when the summation of a degree sequence is odd? $\endgroup$
    – MD_90
    Commented Feb 8, 2015 at 7:21
  • 1
    $\begingroup$ @MD_90 please don't use comments to ask unrelated questions. You can ask them as new questions (though each separately as all of them in one will likely result In closure as "too broad"). $\endgroup$
    – Casteels
    Commented Feb 8, 2015 at 10:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .