tour is also applicable to directed graphs. Mixed Eulerian graphs If a mixed graph has even degrees only, it is not guaranteed to be an Eulerian graph. This means that evenness is a necessary but not sufficient condition for a mixed graph to be Eulerian. If a mixed graph is even and symmetric, it is guaranteed to be symmetric. This means that evenness and being symmetric is a necessary condition for a mixed graph to be Eulerian. This is not a necessary and sufficient condition however, because it is possible to construct a graph that is even and not symmetric that is still Eulerian. Ford and Fulkerson proved in 1962 in their book Flows in Networks a necessary and sufficient condition for a graph to be Eulerian, viz., that every vertex must be even and satisfy the balance condition. For every subset of vertices S, the difference between the number of arcs leaving S and entering S must be less than or equal to the number of edges incident with S. This is the balanced set condition. A mixed and strongly connected graph is Eulerian if and only if G is even and balanced. The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices. See also Eulerian matroid, an abstract generalization of Eulerian graphs Five room puzzle Handshaking lemma, proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree vertices Hamiltonian path – a path that visits each vertex exactly once. Route inspection problem, search for the shortest path that visits all edges, possibly repeating edges if an Eulerian path does not exist. Veblen's theorem, which states that graphs with even vertex degree can be partitioned into edge-disjoint cycles regardless of their connectivity Notes References . Translated as . Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140. . Lucas, E., Récréations Mathématiques IV, Paris, 1921. Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257–261. T. van Aardenne-Ehrenfest and N. G. de Bruijn (1951) "Circuits and trees in oriented linear graphs", Simon Stevin 28: 203–217. W. T. Tutte and C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: