Ear decomposition

In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other. Ear decompositions may be used to characterize several important graph classes, and as part of efficient graph algorithms. They may also be generalized from graphs to matroids. Several important classes of graphs may be characterized as the graphs having certain types of ear decompositions. A graph is k-vertex-connected if the removal of any (k − 1) vertices leaves a connected subgraph, and k-edge-connected if the removal of any (k − 1) edges leaves a connected subgraph. The following result is due to : A graph with is 2-vertex-connected if and only if it has an open ear decomposition. The following result is due to : A graph is 2-edge-connected if and only if it has an ear decomposition. In both cases the number of ears is necessarily equal to the circuit rank of the given graph. Robbins introduced the ear decomposition of 2-edge-connected graphs as a tool for proving the Robbins theorem, that these are exactly the graphs that may be given a strongly connected orientation. Because of the pioneering work of Whitney and Robbins on ear decompositions, an ear decomposition is sometimes also called a Whitney–Robbins synthesis . A non-separating ear decomposition is an open ear decomposition such that, for each vertex v with only one exception, v has a neighbor whose first appearance in the decomposition is in a later ear than the first appearance of v.