10.4 Bridges26310.4 BridgesInthestudyf planargraph, certainsubgraph, calledbridges,play animportanrole. We now define these subgraphs and discuss their properties.Let H be a proper subgraph of a connected graph G. The set E(G) /E(H)may be partitioned into classes as follows.For each component F of G -V(H), there is a class consisting of the edges ofFtogether with the edges linking F to H女Each remaining edge e (that is, one which has both ends in V(H)) defines asingleton class (e].The subgraphs of G induced by these classes are the bridges of H in G. It followsmmediately from this definition that bridges of H can intersect only in verticesof H, and that any two vertices ofabridge of H are connected by a pathin thebridge that is internally disjoint from H. For a bridge B of H, the elements ofV(B) nV(H) are called its vertices of attachment to H; the remaining vertices ofB are its internal vertices. A bridge is trivial if it has no internal vertices (thatis.if it is ofthesecond type). In a connected graph, every bridge has at leastxofattachmenseparable graph, every bridge hastoreoveriat least two vertices of attachment. A bridge with k vertices of attachment iscalled a k-bridge. Two bridges with the same vertices of attachment are equivalentbridges.Figure10.15 shows a variety of bridges ofa cycle in a graph; edgesofdifferent bridges are distinguished by different kinds of lines. Bridges Bi and Bare equivalent 3-bridges; B and Bg are trivial bridges.BsBBAFig. 10.15. Bridges of a cycle10.4 Bridges 263 10.4 Bridges In the study of planar graphs, certain subgraphs, called bridges, play an important role. We now define these subgraphs and discuss their properties. Let H be a proper subgraph of a connected graph G. The set E(G) \ E(H) may be partitioned into classes as follows.  For each component F of G − V (H), there is a class consisting of the edges of F together with the edges linking F to H.  Each remaining edge e (that is, one which has both ends in V (H)) defines a singleton class {e}. The subgraphs of G induced by these classes are the bridges of H in G. It follows immediately from this definition that bridges of H can intersect only in vertices of H, and that any two vertices of a bridge of H are connected by a path in the bridge that is internally disjoint from H. For a bridge B of H, the elements of V (B) ∩ V (H) are called its vertices of attachment to H; the remaining vertices of B are its internal vertices. A bridge is trivial if it has no internal vertices (that is, if it is of the second type). In a connected graph, every bridge has at least one vertex of attachment; moreover, in a nonseparable graph, every bridge has at least two vertices of attachment. A bridge with k vertices of attachment is called a k-bridge. Two bridges with the same vertices of attachment are equivalent bridges. Figure 10.15 shows a variety of bridges of a cycle in a graph; edges of different bridges are distinguished by different kinds of lines. Bridges B1 and B2 are equivalent 3-bridges; B3 and B6 are trivial bridges. B1 B2 B3 B4 B5 B6 Fig. 10.15. Bridges of a cycle