Problem: Eulerian graph
For a
graph oriented, an Eulerian path (or circuit) passes once and only once through all the arcs. Similarly in the undirected case, a chain or Eulerian cycle passes once and only once through all the edges.
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)
Necessary and sufficient conditions of the Eulerian circuit / cycle. The graph is connected (or strongly connected). Whatever a vertex of the graph, its degree is even (its outgoing degree is equal to its entering degree).
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.
Let be a graph admitting an Eulerian chain. Adding an edge between the start and the end of the chain will give us an Eulerian cycle. Likewise, if we remove any edge from an Eulerian cycle, we will have an Eulerian chain.
With this transformation, we deduce the necessary and sufficient conditions for a graph to have an Eulerian chain (or path).
Necessary and sufficient conditions of the Eulerian chain / path. The graph is connected (or strongly connected). For all vertices of the graph, except possibly two, its degree is even (its outgoing degree is equal to its incoming degree + or - 1 for possibly two vertices.
Problem: Hamiltonian graph
In a directed graph, a circuit or a Hamiltonian path is a circuit or path passing once and only once through all the vertices. Likewise for the non-oriented case.
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.
EN 
FR 
ES