3
$\begingroup$

Let $G$ be a simple undirected $k$-connected graph with at least $k+1$ vertices.

  • What ist the least number of vertices, $G$ can have, if it is not hamiltonian ?

    I know Tutte's theorem that every $4$-connected planar graph is hamiltonian, so for $k\ge 4$ only non-planar graphs are possible.

    A lower bound for the number of vertices is $2k+1$ because in a k-connected graph, every vertex has degree at least k, so if the number of vertices is not exceeding $2k$, it must be hamiltonian.

    I am not quite sure, if a graph with the desired property exists for all $k$. If not, what is the least $k$, such that no graph with the desired property exists ?

$\endgroup$
  • 1
    $\begingroup$ Notice that every Hamiltonian graph is $2$-connected so this question only makes sense for $k \ge 3$ $\endgroup$ – Jernej Sep 8 '14 at 11:25
  • $\begingroup$ The smallest example for $k=3$ has 7 vertices. $\endgroup$ – Jernej Sep 8 '14 at 11:33
  • 1
    $\begingroup$ Nevermind - I misunderstood the question. The comment about $k=3$ is still valid though. $\endgroup$ – Jernej Sep 8 '14 at 11:34
  • 1
    $\begingroup$ Here it is dropbox.com/s/xi66y2q2p70cbcs/example.png?dl=0 $\endgroup$ – Jernej Sep 8 '14 at 11:41
4
$\begingroup$

The complete bipartite graph $K_{k,k+1}$ has $2k+1$ vertices and is $k$ connected, but is not Hamiltonian since any path must travel alternately between the two sets of the bipartition and there are not the same number of vertices in each side.

$\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.