Contenus

Toggle## Problem: Eulerian graph

The graph must be strongly connected (or connected). Indeed, if the graph is not, one or more subgraphs containing links cannot be reached. We see that a cycle or Eulerian circuit contains as many links arriving at a vertex as it leaves (we arrive at a vertex to leave)

Since all vertices have an even degree, we know that there is a circuit. A path is a union of disjoint circuits at the edges. If we remove the edges of a path then the degrees are always even. Suppose there is no path giving an Eulerian cycle. If we remove a path with a maximum of edges on the graph then the degrees remain even. But in this case, there is a circuit disjointed from our maximum route. The route being a union of disjoint circuits, we conclude that the initial route was not maximum. Deduces from this that the maximum path contains all the edges of the graph. The proof is identical for the oriented case.

With this transformation, we deduce the necessary and sufficient conditions for a graph to have an Eulerian chain (or path).

## Problem: Hamiltonian graph

To date, there are no necessary and sufficient conditions but only sufficient conditions relating to the degrees of the vertices.

**Dirac 1952.**A simple graph with

**not**vertices (n> 2) each vertex of which has a degree at least equal to n / 2 is Hamiltonian.

**Ore 1960.**A simple graph with not vertices (n> 2) such that the sum of the degrees of any pair of nonadjacent vertices is at least not is Hamiltonian.

**Posa 1962.**A simple graph with

**not**vertices (n> 2) such that for all

**k**, 0 <k<(n-1)/2 le nombre de sommets de degré inférieur ou égal à

**k**is inferior to

**k**. The number of vertices of degree less than or equal to (n-1) / 2 is less than or equal to (n-1) / 2.