Re: Hamiltonian path
From: Curioser (janjaweed_at_excite.com)
Date: 08/01/04
- Next message: |-|erc: "Re: Hawking and Penrose at GR 17 Dublin 2004"
- Previous message: W. Dale Hall: "Re: "Embedded" in the plane."
- In reply to: harry: "Hamiltonian path"
- Messages sorted by: [ date ] [ thread ]
Date: 1 Aug 2004 02:27:20 -0700
If G is a graph such that |V|>3 and each vertex has degree at least
|V|/2, then G must have a hamiltonian circuit. This theorem was proved
by Dirac (Paul Dirac's son) in 1952. For a proof see, for example,
Bondy and Murty's text book: Graph Theory with Applications.
harry <harry@ba.ar> wrote in message news:<cehdld$bq$1@lepsoy.sinectis.com.ar>...
> Someone has a proof for:
> If G = (V, E) is a graph with |V| >= 4, and d_min >= n-2 (d(v) >= n-2 for
> every v in V), then G has a hamiltonian circuit.
> ?
>
> Thanks!
> Harry.
- Next message: |-|erc: "Re: Hawking and Penrose at GR 17 Dublin 2004"
- Previous message: W. Dale Hall: "Re: "Embedded" in the plane."
- In reply to: harry: "Hamiltonian path"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
