2
$\begingroup$

So I'm kinda confused right now and I'm probably just confusing myself for no reason.

So let say we have a graph went just one vertex.

The complete graph of that one vertex will be a loop to itself.

It will have a Euler Circuit because it has a degree of two and starts and ends at the same point.

Am I right?

Also, I think it will have a Hamiltonian Circuit, right?

$\endgroup$
  • $\begingroup$ The complete graph $K_1$ would just be the bare vertex, because $K_n$ is defined for simple graphs, so no loops allowed. $\endgroup$ – Joffan Mar 5 '17 at 22:30
  • $\begingroup$ so there won't be any lines, it just be the vertex itself. So there won't be an Euler Circuit? $\endgroup$ – shawn edward Mar 5 '17 at 22:39
  • $\begingroup$ The path of length zero still counts. $\endgroup$ – JMoravitz Mar 5 '17 at 22:40
  • $\begingroup$ @JMoravitz since zero is a even number, therefore it is a Euler Circuit $\endgroup$ – shawn edward Mar 5 '17 at 22:42
  • 1
    $\begingroup$ To trace the circuit, you put your pencil on the node and say "done" :-) $\endgroup$ – Joffan Mar 5 '17 at 22:46
1
$\begingroup$

Complete graph $K_1$ has $\frac{0\cdot(-1)}{2} = 0$ edges and is Hamiltonian by convention. Also it is connected and all vertex degrees are even (I hope there is no surprise that 0 is even), therefore it is Eulerian.

If you want to consider pseudograph on 1 vertex then it is Hamiltonian and Eulerian, too, since addition/removal a loop doesn't change this properties.

$\endgroup$
  • $\begingroup$ Just to make things clear, a Hamiltonian circuit is when every vertex appears once, so like graph $K2$ would be Hamiltonian because every vertex appears once. $\endgroup$ – shawn edward Mar 5 '17 at 23:10
  • $\begingroup$ No, $K_2$ is not Hamiltonian, because it has no Hamiltonian cycle, since cycle is a closed walk with no repeated edges. $\endgroup$ – Smylic Mar 5 '17 at 23:15
  • $\begingroup$ So it has to have repeated edges to be Hamiltonian? $\endgroup$ – shawn edward Mar 5 '17 at 23:19
1
$\begingroup$

You are right. As there is only one vertex in this graph, and depending on what the graph looks like (a single vertex without an edge or a single vertex with a loop), we find that every top has even degree. It is also trivial to notice that this is a connected graph, so we deduce, by a theorem proven by Euler, that this graph contains an eulerian cyclus. Also, draw both cases and apply your definition of Eulerian cyclus to it! Convince yourself the definition applies here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.