Bridges and Attachments Relative to a Subgraph

Why Bridges Are Defined Relative to a Subgraph

When studying a graph around a chosen subgraph, it is useful to describe the remaining parts by how they meet that subgraph. The same graph can have different bridges when the chosen subgraph changes: the definition is relative, not an intrinsic label for an edge or a component. In particular, a bridge may consist of a single edge joining two vertices of the chosen subgraph, or it may contain vertices outside it.

Throughout, graphs are finite and simple. Let \(G=(V,E)\), and let \(H\) be a subgraph of \(G\), so \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\). The subgraph \(H\) need not be induced: \(G\) may have an edge between two vertices of \(H\) that is not an edge of \(H\). Write \(G-V(H)\) for the subgraph induced by the vertices not in \(H\). A component means a connected component.

For a component bridge, its vertices outside \(H\) are exactly the vertices of \(C\); these are its interior vertices. An attachment is a vertex of \(H\), not an outside vertex. A component bridge can have one attachment, several attachments, or—if \(G\) is disconnected—none. A chord bridge has exactly two distinct attachments because the graph is simple and its edge has two distinct endpoints.

These bridges are not the same as bridges in the sense of cut-edges. Here “bridge” names a subgraph defined relative to \(H\); it does not assert that deleting one of its edges disconnects \(G\).

How the Definition Classifies the Edges

There are two tests to apply. First, if an edge has both endpoints in \(H\) but is not an edge of \(H\), it is a chord bridge. Second, if an edge has at least one endpoint outside \(H\), it belongs to the component bridge determined by the outside component containing that endpoint. Edges with both endpoints in \(H\) that already belong to \(H\) are part of \(H\), not part of any \(H\)-bridge.

Proof. Take any edge \(e\in E(G)\setminus E(H)\). If both endpoints lie in \(V(H)\), then \(e\) is a chord by definition, and that chord is its bridge. If exactly one endpoint, or both endpoints, lie outside \(V(H)\), then the outside endpoint or endpoints lie in the same component \(C\) of \(G-V(H)\): when both are outside, \(e\) itself joins them. Thus \(e\) belongs to the component bridge for \(C\). These cases are mutually exclusive, and each outside vertex belongs to exactly one component of \(G-V(H)\), so the assigned bridge is unique. Different components have disjoint vertex sets, and their bridges can meet only at vertices of \(H\); chord bridges have only vertices in \(H\). Therefore distinct bridges have disjoint interior vertices and can share only vertices of \(H\). \(\square\)

A useful consequence of the definition is that each component bridge is connected. Its component \(C\) is connected, and every included edge from \(C\) to \(H\) attaches an endpoint in \(H\) directly to \(C\). If there are no such edges, the bridge is just the connected component \(C\). A chord bridge is also connected, since it consists of one edge and its endpoints.

Proof. Let \(C\) be a component of \(G-V(H)\), and choose a vertex \(x\in C\). Since \(G\) is connected and \(H\) has a vertex, there is a path in \(G\) from \(x\) to a vertex of \(H\). Along this path, take the first edge that leaves \(C\). Its endpoint outside \(C\) cannot be in another component of \(G-V(H)\), because an edge between two outside vertices would put them in the same component. Therefore that endpoint lies in \(H\), and the edge is one of the edges from \(C\) to \(H\). Its endpoint in \(H\) is an attachment of the bridge. \(\square\)

Attachments Record the Interface

The attachment set records where a bridge meets \(H\), not every vertex or edge in the bridge. In a component bridge, the edges from the outside component to \(H\) determine its attachments. A vertex of \(H\) is an attachment if at least one such edge is incident with it. If two or more outside edges meet the same vertex of \(H\), that vertex still appears only once in the attachment set.

A bridge with one attachment is possible even when \(G\) is connected: it can meet the rest of the graph at a single vertex of \(H\). Two different bridges may also have the same attachment set. The attachments identify the interface of each bridge with \(H\), not the bridge’s full internal structure.

Common Pitfall: Treating Every Edge Near \(H\) the Same Way

A frequent error is to call an edge a component bridge merely because it is not in \(H\). That misses the distinction between edges whose two endpoints are already in \(H\) and edges that involve vertices outside \(H\). For example, in the first worked example, the edge \(13\) is not in the cycle \(H\), but both \(1\) and \(3\) are vertices of \(H\). It is a chord bridge with attachments \(\{1,3\}\), not part of either outside-component bridge. The edge \(25\), by contrast, has endpoint \(5\) outside \(H\), so it belongs to the component bridge for the outside component containing \(5\).

Another error is to treat \(H\) as induced without checking. In the second example, doing so would erase the chord bridges \(13,14,24\) from the classification. The correct test is whether an edge lies in the specified set \(E(H)\), not whether its endpoints happen to be in \(V(H)\).

Bridge decomposition is useful because it separates the portions of \(G\) outside \(H\) while recording exactly where each portion meets \(H\). The classification is complete at the edge level: every edge not already in \(H\) belongs to one bridge, and different bridges have no common interior vertices. Keeping the bridge and its attachment set distinct makes this information precise and avoids confusing the internal structure of a bridge with its interface to the chosen subgraph.