A walk in a graph is a list of edges where the final endpoint of each edge, other than the last, is the initial point of the next one. Of course for an undirected graph we don’t have to worry about which vertex is the initial vertex and which is the final vertex of an edge, since there is always another edge with the opposite orientation. You can check that the edges \({ ( a , b ) }\), \({ ( b , c ) }\) \({ ( c , d ) }\), \({ ( d , e ) }\), \({ ( e , f ) }\), \({ ( f , g ) }\), \({ ( g , h ) }\), \({ ( h , i ) }\), \({ ( i , j ) }\), \({ ( j , k ) }\), \({ ( k , l ) }\) form a path of length 11. It’s more efficient to list the vertices in order than to list the edges though to avoid listing vertices twice, once as the initial endpoint of an edge and once as the final endpoint. The walk above would then be given by the list of vertices \({ ( a , b , c , d , e , f , g , h , i , j , k , l ) }\). Note that the number of vertices in such a list is always one greater than the number of edges.
A walk in an undirected graph, like the one above, is called a trail if at most one from each pair of edges appears and is called a path if each edge appears at most once. The walk above is both a trail and a path. It can be extended further as a trail but not as a path. We could, for example, extend the path further by adding the edge \({ ( l , j ) }\) to get a trail of length 12, but this would not be a path since the vertex \({ j }\) would appear twice. In fact there can’t be a trail of length 12 in this graph because the number of vertices appearing in a trail is one greater than the length and this graph only has 12 vertices.
A walk is called closed if it starts and ends with the same vertex. The walk above is not closed, but it can be extended to a closed walk, which visits the vertices in the order given by the following list: \({ ( a , b , c , d , e , f , g , h , i , j , k , l , j , e , k , g , l , h , c , i , d , a ) }\). This is a closed path of length 21. It is in fact a trail. Closed trails are called circuits.
How long could a circuit in this graph be? The number of edges is the sum of the degrees of the vertices and there are twelve vertices, each of degree 5, so there are 60 edges, or 30 pairs of edges, so no trail could possibly have length greater than 30. In fact we can’t even have one that long. The number times a vertex appears as the initial vertex of an edge in a circuit must be equal to the number times it appears as a final vertex and there are only five pairs of edges for each vertex so the we can’t have more than two incoming and two outgoing edges appearing in a circuit. With 12 vertices there therefore can’t be more than 24 edges.
Suppose a non-empty undirected graph has all vertices of degree at least 2. Then it has a simple circuit. We can see this as follows. Given any vertex \({ v }\) of degree at least two there is a pair of distinct edges through \({ v }\). Taking one and then the other gives a path length two passing through \({ v }\). Consider the set of paths through \({ v }\). The length of such a path is at most the number of vertices in the graph. There is therefore a longest such path. The final point of the path has degree at least two and only one of the edges it traverses is in the path, since the path has no repeated vertices. Adding that edge gives a longer walk, but it can’t give a longer path, since we’ve already chosen one of maximal length. The other vertex of the edge we’ve added must then be one of the vertices already in the path. Following from that vertex along the path and then back along the edge we’ve just added gives a simple circuit.
Another case in which we know there is a non-trivial simple circuit is when there are two vertices connected by distinct paths. We can get a closed path by following one path in the forward direction and the other in the reverse direction, but that walk need not be a circuit, let alone a simple circuit. We can, however, look at the first vertex where the two paths diverge and the first vertex after that where they come together again. If we look only at the parts of the paths between those two vertices then we can still follow one in the forward direction and the other in the reverse direction. This time the resulting closed walk will be a simple circuit.
A trail or circuit is called Eulerian if exactly one from each pair of edges appears. Our example graph has no Eulerian path or circuit. We’ve seen that there are 30 edges and no circuit can be of length greater than 24. A slight modification of the argument which showed that also tells us that no path has length greater than 25. To get an example we therefore need to look at a different graph. Our bipartite graph example will work. This is a regular graph with 12 vertices, each of degree 6. There are therefore 36 pairs of edges, so a circuit of length 36 must be Eulerian. One such example is the graph which visits the vertices \({ abcd }\), \({ cadb }\), \({ acdb }\), \({ dabc }\), \({ abcd }\), \({ abdc }\), \({ bcad }\), \({ cadb }\), \({ cabd }\), \({ adcb }\), \({ dacb }\), \({ abdc }\), \({ cabd }\), \({ acbd }\), \({ acdb }\), \({ adcb }\), \({ adbc }\), \({ bcda }\), \({ bcad }\), \({ acbd }\), \({ adbc }\), \({ dabc }\), \({ dacb }\), \({ bcda }\), \({ abcd }\), \({ acbd }\), \({ dacb }\), \({ cadb }\), \({ adbc }\), \({ abdc }\), \({ acdb }\), \({ bcda }\), \({ cabd }\), \({ dabc }\), \({ bcad }\), \({ adcb }\), and \({ abcd }\) in that order.