Graph theory began in the year 1736 when Leonard Euler published a paper that contained the solution to the 7 bridges of Königsberg problem. Is it possible to take a walk around town crossing each bridge exactly once and wind up at your starting point?

The object is to cross each bridge exactly once on a walk that begins and ends in the same spot (vertex). Such a traversal would be a closed trail (a circuit) since the edges are distinct and the number of times each vertex (landmass) is encountered is not under consideration. When a (multi)graph is so traversable it is said to be Eulerian and possesses an Eulerian circuit. An Eulerian trail is a walk that contains all the edges (exactly once) but is not closed.

Any alternating sequence of vertices and incident edges in a graph is known as a walk. A walk begins and ends with vertices. The listing can be made by alternating vertices and edges or just by listing the sequence of adjacent vertices. The length of the walk is the number of edges. A walk is said to be closed if the beginning and ending vertices are the same.

A trail is a walk with distinct edges. The distinction between path and trail varies by the author, as do many of the nonstandardized terms that make up graph theory. Epp considers a trail a path and the case of distinct vertices she calls a simple path. We shall use the terms trail and path synonymously and refer to the case of distinct vertices as either a simple trial or a simple path.

A circuit is a closed walk that does not contain any repeated edges. A circuit is therefore a closed path. A simple circuit is a closed walk that does not contain any repeated edges or repeated vertices except of course the first and last.

A graph is said to be connected iff there is a path between every pair of vertices.

We sometimes remove from a graph a vertex, v, and all of its incident edges. The resulting graph, G’ = G –{v}, will have drastically altered structure. If the deletion of v and all its incident edges makes an originally connected graph disconnected then v is known as a cut point or as a cut vertex.

If we delete an edge, e, and an originally connected graph becomes disconnected, then e is a bridge. Let G be a connected graph. An edge e of G is a bridge of G iff e does not lie in any cycle of G.

A component of a graph G(V, E) is a connected subgraph G’(V’, E’) such that no vertex in V’ is connected to any vertex outside V’ in G. So any graph is connected iff it consists of only one component.

Let G be a graph.

1. If G is connected, then any two distinct vertices of G can be connected by a simple path.
2. If vertices v and w are part of a circuit in G and one edge is remove from the circuit, then there still exists a path from v to w in G.
3. If G is connected and G contains a circuit, then an edge of the circuit can be removed without disconnecting G.

A connected (multi)graph G is Eulerian (has a circuit containing every edge) iff every vertex of G is even.

Proof: Each occurrence of a given vertex in the circuit C contributes 2 to the degree of the vertex since the circuit must enter and leave the vertex by different edges. Since each edge appears exactly once in C, then every vertex must have even degree. Now to show the converse; that is, if each vertex of G has even degree, then there will be an Eulerian circuit.

1. Start the construction of C at any arbitrary vertex v of G.
2. From v, choose any edge and continue to wander among the vertices of G using only unused edges. When a vertex w is reached out of which there are no unused edges, we claim that a cycle has been constructed; that is, vertex w = vertex v. Now to substantiate the claim that w = v, we assume to the contrary that w ¹ v. Each previous occurrence of vertex w in C used one edge to enter and a different edge to exit. On this last entry to vertex w only one edge has been used. Since w has even degree, then there must be at least one edge incident with w not on circuit C, which means that C can be continued, and thus does not terminate at vertex w. Thus by contradiction vertex w = vertex v. If C now contains all edges in G then C is Eulerian and we are done.
3. Since G is connected there is at least one vertex, u, on C that is incident with edges not on C. Remove all edges on C from G to get G’ = G – E(C). Every vertex of G’ is even since every vertex of G was even. Choose u to begin a new circuit as in step 2.
4. Continue steps 2 and 3 a finite number of times to construct an Eulerian circuit.

Let g be a graph and let v and w be two vertices of G. An Euler path from v to w is a sequence of adjacent edges and vertices that starts at v, ends at w, passes through every vertex of G at least once, and traverses every edge of G exactly once.

Let G be a graph and let v and w be two vertices of G. There is an Euler path from v to w iff G is connected, v and w have odd degree, and all other vertices of G have even degree.

Clearly each vertex has odd degree. There is neither an Eulerian Circuit nor an Eulerian Path.

Definition: Hamiltonian Circuit
Given a graph G, a Hamiltonian circuit for G is a simple circuit that includes every vertex of G. That is, a Hamiltonian circuit for G is a sequence of adjacent vertices and distinct edges in which every vertex of G appears exactly once.

Note that for an Euler circuit a graph G must include every vertex of G, it may visit some vertices more than once and hence may not be a Hamiltonian circuit. On the other hand, a Hamiltonian circuit for G does not need to include all the edges of G and hence may not be an Euler circuit. Look at figure 11.2.13 on p. 633. The outlined (highlighted) circuit is a subgraph of G. Call this circuit H, it is a simple circuit that includes every vertex of G and is therefore Hamiltonian.

Despite the similar sounding definitions of Euler and Hamiltonian circuits, the mathematics of the two are very different. Consider the traveling salesperson problem, example 11.2.9. Finding a minimal route passing through every city once and winding up at home is analogous to finding a Hamiltonian circuit. The only way to guarantee the best solution is to write down every possible simple circuit and evaluate the distances of each to determine the best. While verification of the solution to this algorithm is of polynomial order, this non-deterministic plan of attack for something as simple as K₃₀  would require generation of 29! Hamiltonian circuits and checking each against the shortest path (~2.8 x 10¹⁴ years at one operation per nanosecond). To date the best algorithms only find "pretty good" solutions in reasonable time for large data sets.

Proposition 11.2.6
If a graph G has a Hamiltonian circuit then G has a subgraph H with the following properties:

1. H contains every vertex of G;
2. H is connected;
3. H has the same number of edges as vertices;
4. Every vertex of H has degree 2.

What is the contrapositive of Proposition 11.2.6?