Hubbry Logo
Bridge (graph theory)Bridge (graph theory)Main
Open search
Bridge (graph theory)
Community hub
Bridge (graph theory)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Bridge (graph theory)
Bridge (graph theory)
Bridge (graph theory)
View on Wikipedia
from Wikipedia
A graph with 16 vertices and six bridges (highlighted in red)
An undirected connected graph with no bridge edges

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components.[1] Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see bridge in the Glossary of graph theory.

Trees and forests

[edit]

A graph with nodes can contain at most bridges, since adding additional edges must create a cycle. The graphs with exactly bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests.

In every undirected graph, there is an equivalence relation on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called 2-edge-connected components, and the bridges of the graph are exactly the edges whose endpoints belong to different components. The bridge-block tree of the graph has a vertex for every nontrivial component and an edge for every bridge.[2]

Relation to vertex connectivity

[edit]

Bridges are closely related to the concept of articulation vertices, vertices that belong to every path between some pair of other vertices. The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints. Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are 2-vertex-connected.

In a cubic graph, every cut vertex is an endpoint of at least one bridge.

Bridgeless graphs

[edit]

A bridgeless graph is a graph that does not have any bridges. Equivalent conditions are that each connected component of the graph has an open ear decomposition,[3] that each connected component is 2-edge-connected, or (by Robbins' theorem) that every connected component has a strong orientation.[3]

An important open problem involving bridges is the cycle double cover conjecture, due to Seymour and Szekeres (1978 and 1979, independently), which states that every bridgeless graph admits a multi-set of simple cycles which contains each edge exactly twice.[4]

Tarjan's bridge-finding algorithm

[edit]

The first linear time algorithm (linear in the number of edges) for finding the bridges in a graph was described by Robert Tarjan in 1974.[5] It performs the following steps:

  • Find a spanning forest of
  • Create a Rooted forest from the spanning forest
  • Traverse the forest in preorder and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
  • For each node in preorder (denoting each node using its preorder number), do:
    • Compute the number of forest descendants for this node, by adding one to the sum of its children's descendants.
    • Compute , the lowest preorder label reachable from by a path for which all but the last edge stays within the subtree rooted at . This is the minimum of the set consisting of the preorder label of , of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to .
    • Similarly, compute , the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at . This is the maximum of the set consisting of the preorder label of , of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to .
    • For each node with parent node , if and then the edge from to is a bridge.

Bridge-finding with chain decompositions

[edit]

A very simple bridge-finding algorithm[6] uses chain decompositions. Chain decompositions do not only allow to compute all bridges of a graph, they also allow to read off every cut vertex of G (and the block-cut tree of G), giving a general framework for testing 2-edge- and 2-vertex-connectivity (which extends to linear-time 3-edge- and 3-vertex-connectivity tests).

Chain decompositions are special ear decompositions depending on a DFS-tree T of G and can be computed very simply: Let every vertex be marked as unvisited. For each vertex v in ascending DFS-numbers 1...n, traverse every backedge (i.e. every edge not in the DFS tree) that is incident to v and follow the path of tree-edges back to the root of T, stopping at the first vertex that is marked as visited. During such a traversal, every traversed vertex is marked as visited. Thus, a traversal stops at the latest at v and forms either a directed path or cycle, beginning with v; we call this path or cycle a chain. The ith chain found by this procedure is referred to as Ci. C=C1,C2,... is then a chain decomposition of G.

The following characterizations then allow to read off several properties of G from C efficiently, including all bridges of G.[6] Let C be a chain decomposition of a simple connected graph G=(V,E).

  1. G is 2-edge-connected if and only if the chains in C partition E.
  2. An edge e in G is a bridge if and only if e is not contained in any chain in C.
  3. If G is 2-edge-connected, C is an ear decomposition.
  4. G is 2-vertex-connected if and only if G has minimum degree 2 and C1 is the only cycle in C.
  5. A vertex v in a 2-edge-connected graph G is a cut vertex if and only if v is the first vertex of a cycle in C - C1.
  6. If G is 2-vertex-connected, C is an open ear decomposition.

Bridges and Eulerian cycles

[edit]

Define an Eulerian graph as a graph with an Eulerian cycle. Every Eulerian graph is bridgeless. This is because in an Eulerian graph every edge is a part of an Eulerian cycle. Hence, if the edge is deleted, then its endpoints remain connected through the rest of the cycle. But the opposite is not true.

Define an almost Eulerian graph as a graph that can be made Eulerian by adding a single edge (equivalently, a graph that contains an Eulerian trail). Every almost-Eulerian graph is almost-bridgeless, but the opposite is not true.

The classes of bridgeless graphs and almost-Eulerian graphs have a non-empty intersection (the Eulerian graphs are both bridgeless and almost-Eulerian), but they do not contain each other.[7]: Appendix.B 

See also

[edit]

Notes

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Bridge (graph theory)

View on Grokipedia
from Grokipedia
In , a bridge, also known as a cut-edge, , or cut arc, is an edge in a graph whose removal increases the number of connected components. This property distinguishes bridges as critical links that maintain the graph's connectivity, and they exist only in edges that do not lie on any cycle. For instance, in a —a connected acyclic graph—every edge is a bridge, as removing any edge disconnects the structure into two components. Bridges play a fundamental role in understanding graph robustness and are essential in applications such as network design, where identifying them helps pinpoint single points of failure in communication or transportation systems. A graph containing at least one bridge is termed a bridged graph, while a bridgeless graph has no such edges and is 2-edge-connected, meaning it remains connected after removing any single edge. Related concepts include articulation points (or cut-vertices), which are vertices whose removal similarly increases connected components, often appearing alongside bridges in analyses of graph vulnerability. Efficient algorithms exist for detecting bridges, with Tarjan's (DFS)-based method achieving linear O(V + E), where V is the number of vertices and E is the number of edges. This , introduced in , leverages discovery times and low-link values during DFS traversal to identify bridges without explicitly checking cycles. Bridges also feature in theorems on graph connectivity; for example, in a connected , the presence of a bridge implies an articulation vertex. Overall, studying bridges aids in decomposing graphs into 2-edge-connected components, facilitating broader structural analysis in and .

Fundamentals

Definition

In graph theory, consider an undirected graph G=(V,E)G = (V, E). An edge e∈Ee \in E is defined as a bridge if its removal from GG increases the number of connected components in the resulting graph G−eG - e. This definition captures edges that are critical to the graph's connectivity, as their absence disconnects previously connected vertices. Equivalent characterizations of a bridge provide deeper insight into its structural role. Specifically, an edge uv∈Euv \in E is a bridge if and only if it is not contained in any cycle of GG; alternatively, there exists no path from uu to vv in G−uvG - uv. The set of all bridges in GG is denoted by B(G)B(G). The term "bridge" for such edges was introduced by J. A. Bondy and U. S. R. Murty in their 1976 textbook Graph Theory with Applications. To illustrate, consider simple examples: in the graph consisting of a single edge connecting two vertices, that edge is a bridge, as its removal yields two isolated vertices and thus two components. In a path graph with n≥2n \geq 2 vertices (and n−1n-1 edges), every edge is a bridge, since removing any disconnects the path into two components. Conversely, in a cycle graph with n≥3n \geq 3 vertices, no edge is a bridge, as the remaining cycle path connects all vertices after removal.

Basic Properties

A bridge in a graph is precisely an edge that does not lie on any simple cycle. This property follows directly from the definition, as the absence of an alternative path between its endpoints ensures that removing the edge disconnects the graph. Removing all bridges from a connected graph decomposes it into its 2-edge-connected components, which are maximal subgraphs with no bridges of their own. These components are connected by the bridges, forming a tree-like structure in the block-bridge graph. In a connected graph with nn vertices, the number of bridges is at most n−1n-1, with equality holding when the graph is a . Bridges exhibit invariance under certain graph modifications: specifically, adding edges within the same 2-edge-connected component does not create a cycle through an existing bridge, preserving its status as a bridge. For example, consider a graph formed by two disjoint cycles joined by a single edge; this connecting edge is a bridge, as its removal separates the cycles into distinct components, while the cycle edges are not bridges.

Structural Aspects

Bridges in Trees and Forests

In trees, which are connected acyclic graphs, every edge qualifies as a bridge because trees are minimally connected structures with no redundant paths. Removing any edge from a disconnects it, splitting the graph into exactly two connected components, as there exists a unique path between any pair of vertices and no cycles to provide alternative connections. To see this formally, suppose TT is a with nn vertices and consider an arbitrary edge e=uve = uv. The removal of ee yields two components: one containing uu and the other containing vv. If T−eT - e remained connected, there would exist a path from uu to vv avoiding ee, which together with ee would form a cycle, contradicting the acyclicity of TT. Thus, every edge in a is indeed a bridge. A generalizes this to disconnected acyclic graphs, where each connected component is a . In such a , every edge is a bridge, as all edges lie within individual tree components and satisfy the bridge property therein; there are no edges between components by definition. For a with nn vertices and kk components, the total number of edges is exactly ∣E∣=n−k|E| = n - k, and thus the number of bridges equals n−kn - k, comprising all edges in the graph. For example, consider a forest consisting of mm isolated trees on nn vertices total. This structure has precisely n−mn - m edges, each of which is a bridge, underscoring the minimal connectivity inherent to acyclic graphs.

Relation to Connectivity

In graph theory, the presence of a bridge in a connected graph GG fundamentally affects its edge connectivity λ(G)\lambda(G), which is the size of the minimum edge cut. Specifically, if GG contains at least one bridge, then λ(G)=1\lambda(G) = 1, as removing that single edge disconnects the graph. Conversely, a connected graph GG has no bridges if and only if it is 2-edge-connected, meaning λ(G)≥2\lambda(G) \geq 2. This equivalence highlights bridges as the critical edges that limit edge connectivity to its lowest non-trivial value. Whitney's theorem provides a broader framework for understanding these relations in connected graphs: the vertex connectivity κ(G)\kappa(G) satisfies κ(G)≤λ(G)≤δ(G)\kappa(G) \leq \lambda(G) \leq \delta(G), where δ(G)\delta(G) is the minimum degree. Thus, bridges not only force λ(G)=1\lambda(G) = 1 but also imply κ(G)≤1\kappa(G) \leq 1, since the graph can be disconnected by removing a single edge and, consequently, by removing vertices incident to it. This follows from , which equates the minimum size of a vertex separator between non-adjacent vertices ss and tt to the maximum number of internally vertex-disjoint paths between them; a bridge partitions the graph into components where such paths between vertices on opposite sides number at most one, yielding a vertex separator of size 1. However, the absence of bridges guarantees only λ(G)≥2\lambda(G) \geq 2 and does not ensure λ(G)=δ(G)\lambda(G) = \delta(G) or high vertex connectivity. For instance, κ(G)\kappa(G) may still equal 1 if articulation points exist, even without bridges, as vertex cuts can be smaller than edge cuts in non-2-vertex-connected graphs. Consider a graph consisting of two complete graphs K3K_3 connected by a single edge (a bridge): here, δ(G)=2\delta(G) = 2 in the cycles but λ(G)=1\lambda(G) = 1, demonstrating that bridges override degree considerations to cap connectivity at 1, regardless of local vertex degrees.

Algorithms

Depth-First Search Approaches

Depth-first search (DFS) provides a foundational framework for detecting bridges in an undirected graph by constructing a spanning tree and examining the connectivity of subtrees through back edges. The approach begins with a DFS traversal starting from an arbitrary vertex, which builds a DFS tree where tree edges represent the paths taken during exploration, and back edges connect a vertex to one of its ancestors in the tree. This classification of edges is essential, as bridges can only occur among tree edges, while back edges indicate alternative paths that preserve connectivity. To identify potential bridges, each vertex uu receives a discovery time \disc\disc, assigned as a unique timestamp incremented sequentially upon first visiting uu during the traversal. Complementing this, a low value \low\low is computed for each vertex, defined as the smallest discovery time reachable from uu or any descendant in its subtree, accounting for both tree edges and back edges from those descendants. The low value thus captures the earliest accessible from the subtree without relying solely on the parent edge. A tree edge uvuv, where vv is a child of uu in the DFS tree, qualifies as a bridge if \low>\disc\low > \disc. This condition signifies that no vertex in the subtree rooted at vv has a back edge to an ancestor of uu, implying that removing uvuv would disconnect the subtree from the rest of the graph. By checking this inequality after recursing on each child, all bridges are identified during the single DFS pass. The entire process operates in linear time, specifically O(∣V∣+∣E∣)O(|V| + |E|), where ∣V∣|V| is the number of vertices and ∣E∣|E| is the number of edges, as it requires only one traversal to visit all vertices and examine all edges. This efficiency stems from the constant-time operations per edge and vertex in updating timestamps and low values. The algorithm is typically implemented via a recursive procedure that tracks the parent to prevent immediate and initializes arrays for discovery times, low values, and parent pointers, all set to -1 or as appropriate before starting. Here is an outline of the core :

time = 0 disc = [array](/page/Array) of size |V| initialized to -1 low = array of size |V| initialized to -1 parent = [array](/page/Parent) of size |V| initialized to -1 procedure DFS(u): disc[u] = low[u] = time time += 1 for each neighbor v of u: if disc[v] == -1: // v is unvisited parent[v] = u DFS(v) low[u] = min(low[u], low[v]) if low[v] > disc[u]: mark edge (u, v) as a bridge elif v != parent[u]: // back edge low[u] = min(low[u], disc[v]) // Call DFS(start) for each unvisited start vertex to handle disconnected graphs

time = 0 disc = [array](/page/Array) of size |V| initialized to -1 low = array of size |V| initialized to -1 parent = [array](/page/Parent) of size |V| initialized to -1 procedure DFS(u): disc[u] = low[u] = time time += 1 for each neighbor v of u: if disc[v] == -1: // v is unvisited parent[v] = u DFS(v) low[u] = min(low[u], low[v]) if low[v] > disc[u]: mark edge (u, v) as a bridge elif v != parent[u]: // back edge low[u] = min(low[u], disc[v]) // Call DFS(start) for each unvisited start vertex to handle disconnected graphs

This procedure must be invoked from each unvisited vertex to ensure the entire graph, including disconnected components, is processed, though bridges are only relevant within connected components.

Tarjan's Algorithm

Tarjan's algorithm for finding bridges in an undirected graph is a (DFS)-based method that identifies all bridges in linear time, O(V + E), where V is the number of vertices and E is the number of edges. It extends the basic DFS traversal by maintaining two key values for each vertex: the discovery time, which records the order in which vertices are first visited, and the low value, which represents the smallest discovery time reachable from that vertex, including itself and its descendants in the DFS tree, considering back edges. This approach allows direct detection of bridges during a single DFS pass over the graph, handling disconnected components by initiating DFS from each unvisited vertex to form a DFS forest. The key innovation of Tarjan's algorithm lies in its use of the low and discovery values to pinpoint bridges without needing additional structures like stacks for path tracking, distinguishing it from earlier DFS variants by enabling efficient identification in one traversal. To implement it, initialize two arrays, disc[] and low[], to -1 (indicating unvisited), along with a global timer set to 0 and a parent array for tracking the DFS tree. For each unvisited vertex u, call the DFS procedure on u. In the DFS(u) procedure:
  • Set disc = low = timer and increment timer.
  • For each adjacent vertex v of u:
    • If v is unvisited (disc == -1), set parent = u, recursively call DFS(v), then update low = min(low, low).
    • If low > disc after the recursion, mark the edge (u, v) as a bridge, as no path exists from v's subtree back to u or its ancestors without this edge.
    • Else if v != parent (indicating a back edge), update low = min(low, disc).
This process repeats for all neighbors, ensuring low captures the earliest reachable discovery time via tree edges to descendants or back edges to ancestors. Back edges, which connect a vertex to an ancestor in the DFS tree, are crucial for updating low values and preventing false bridge identifications; specifically, when encountering such an edge (u, w) where w is visited and not the parent, the low is minimized with disc, propagating reachability information up the tree. The correctness of the bridge detection relies on the condition low > disc for a tree edge (u, v): this indicates that v and its subtree have no back edge to any vertex discovered before u, meaning (u, v) is the only path connecting the subtree to the rest of the graph, and removing it would disconnect the components. If a back edge or a path through descendants provides an alternative route (low ≤ disc), the edge is not a bridge. The algorithm was first described by in his 1974 paper "A note on finding the bridges of a graph," where it is presented as an efficient solution for the problem in connected undirected graphs, extensible to disconnected ones via multiple DFS starts. For example, consider an undirected graph with vertices A, B, C, D, and edges forming a cycle A-B-C-A plus a pendant edge B-D. Starting DFS at A (disc[A]=0), visit B (disc[B]=1), then from B visit D (disc[D]=2, low[D]=2). Since D has no further edges, low[D] > disc[B] (2 > 1), so B-D is marked a bridge. Backtracking to B, then to C (disc[C]=3, low[C]=3), but from C a back edge to A updates low[C] = min(3, disc[A]=0) = 0. Then low[B] updates to min(1, low[C]=0) = 0, and since low[C] ≤ disc[B] (0 ≤ 1), B-C is not a bridge. Similarly, other cycle edges are not bridges, confirming only B-D as the bridge.

Chain Decomposition Methods

Chain decomposition methods provide an alternative approach to identifying bridges in an undirected graph by partitioning the edge set into edge-disjoint chains, where a chain is either a path or a cycle, and bridges correspond to edges that form singleton chains (i.e., isolated edges not part of any longer chain). This decomposition reveals the structural properties related to 2-edge-connectivity, as a graph is 2-edge-connected all edges are covered by chains of length at least 2. A foundational for computing such a , building on (DFS), was proposed by Jens M. Schmidt in 2013. The method begins by performing a DFS on the graph to construct a and assign depth-first indices (DFIs) to vertices. Tree edges are oriented toward the root, and backedges away from it. Then, for each vertex in ascending DFI order, the traverses cycles formed by backedges incident to that vertex, marking visited vertices and edges to build chains until a previously visited vertex is reached. This process partitions the edges into O(|E| - |V| + 1) chains in linear time, O(|V| + |E|). Bridges are identified as those edges not included in any chain, effectively isolating them as length-1 chains. The approach leverages st-numbering concepts from Even and Tarjan's work, which facilitates systematic path and cycle constructions in biconnected subgraphs. An alternative method, proposed by John Hopcroft and Robert E. Tarjan, integrates chain-like decompositions with identification. By computing the via DFS and low-value tracking, the algorithm isolates bridges as the single-edge components that connect larger biconnected subgraphs, effectively revealing a where bridges serve as linking edges. This yields the same linear-time complexity, O(|V| + |E|), and supports further decompositions into paths by contracting cycles into supervertices, leaving bridges as the remaining tree edges. For example, consider a graph consisting of two cycles joined by a single edge: the forms chains that fully cover each cycle, while the joining edge stands alone as a singleton chain, confirming its status as a bridge. These methods, emerging in the 1970s, were pivotal for efficient parallelizable computations of bridges and biconnected structures, influencing subsequent algorithms for connectivity testing.

Applications

Bridgeless Graphs

A bridgeless graph is a connected graph that contains no bridges, meaning the removal of any single edge leaves the graph connected; this property is equivalent to the graph being 2-edge-connected. Such graphs form a fundamental class in , as they ensure robustness against single-edge failures, distinguishing them from graphs with bridges that serve as critical links. A key characterization of bridgeless graphs is their equivalence to connected graphs admitting an ear : a partitioning of the edge set into a sequence beginning with a cycle, followed by paths (called ears) whose internal vertices are new and endpoints lie in the previously constructed subgraph. This , introduced in the context of connectivity proofs, underscores the cyclic structure inherent in bridgeless graphs, where every edge participates in at least one cycle. The number of ears in such a equals the cyclomatic number, ∣E∣−∣V∣+1|E| - |V| + 1, providing a structural measure of the graph's complexity. Petersen's theorem establishes a significant property for a subclass of bridgeless graphs: every cubic (3-regular) bridgeless graph contains a , pairing all vertices via non-adjacent edges. Proven in , this result relies on the absence of bridges to guarantee the matching's existence, though it applies specifically to cubic graphs and does not extend directly to bridgeless graphs of arbitrary degree. The has implications for matching and flows in regular graphs without bridges. In applications to network design, bridgeless graphs ensure fault-tolerant edge connectivity, allowing networks to remain operational after the failure of any individual link, which is vital for reliable communication systems and modeling. For instance, designing telecommunication or transportation networks as bridgeless structures minimizes single-point failures in edge connectivity. Examples include complete graphs KnK_n for n≥3n \geq 3, where multiple edges between vertices prevent bridges, and cycle graphs CnC_n for n≥3n \geq 3, which are minimally bridgeless; in contrast, trees are replete with bridges and thus not bridgeless. Bridgeless graphs also relate to snarks, which are minimal cubic bridgeless graphs that are non-3-edge-colorable, serving as counterexamples to conjectures on edge colorings and highlighting the boundaries of Tait colorability in cubic graphs. These graphs, often cyclically 4-edge-connected, underscore theoretical challenges in coloring bridgeless structures beyond basic connectivity.

Bridges and Eulerian Cycles

A connected graph has an Eulerian cycle if and only if every vertex has even degree. This condition ensures the graph is 2-edge-connected, meaning it contains no bridges. The presence of a bridge in a connected graph precludes the existence of an Eulerian cycle, as a bridge cannot be traversed in a closed tour that returns to the starting vertex without reusing edges. This disruption arises because removing the bridge disconnects the graph, and an Eulerian cycle must maintain connectivity while covering all edges exactly once, which is impossible if the bridge's endpoints would otherwise require an odd-degree adjustment in the components. Veblen's theorem extends this understanding by stating that a connected graph admits a into edge-disjoint cycles it is Eulerian (i.e., every vertex has even degree). Since bridges are edges not contained in any cycle, their existence forces a non-Eulerian structure even if all degrees are even elsewhere, preventing such a cycle . For Eulerian paths (which need not be closed), a connected graph has such a path if and only if exactly zero or two vertices have odd degree. Unlike cycles, bridges do not universally prohibit Eulerian paths; for instance, a graph consisting of two Eulerian subgraphs connected by a single bridge, where the bridge endpoints are the only odd-degree vertices, admits an Eulerian path starting at one odd-degree vertex, traversing one subgraph, crossing the bridge, and ending in the other subgraph. However, if the graph is not a single path and contains bridges that isolate components incompatible with the degree condition, no Eulerian path exists. Consider a figure-eight graph, formed by two cycles sharing a single vertex; all vertices have even degree, the graph is bridgeless, and it possesses an Eulerian cycle that traverses both loops seamlessly. Attaching a pendant edge to one vertex introduces a bridge and creates two odd-degree vertices (the pendant's endpoint and the attachment point), eliminating the Eulerian cycle while permitting an from the pendant endpoint to the attachment point. In practice, detecting bridges via algorithms like can preprocess a graph to verify the absence of bridges before applying degree checks for Eulerian cycle existence, providing an efficient confirmation of 2-edge-connectivity.

References

  1. https://mathworld.wolfram.com/GraphBridge.html
  2. https://www.geeksforgeeks.org/dsa/bridge-in-a-graph/
  3. https://www.cp-algorithms.com/graph/bridge-searching.html
  4. https://www.zib.de/userpage/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf
  5. https://math.arizona.edu/~kglasner/math443/BondyMurtyGTWA.pdf
  6. https://courses.grainger.illinois.edu/cs473/fa2011/hw/hw_01.pdf
  7. https://diestel-graph-theory.com/
  8. https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch3.pdf
  9. https://www.jstor.org/stable/2371086
  10. https://eudml.org/doc/211191
  11. https://epubs.siam.org/doi/10.1137/0201010
  12. https://doi.org/10.1016/0020-0190(74)90003-9
  13. https://arxiv.org/abs/1209.0700
  14. https://doi.org/10.1016/j.ipl.2013.01.016
  15. https://mathworld.wolfram.com/BridgelessGraph.html
  16. https://math.mit.edu/~goemans/18438F09/lec4.pdf
  17. https://www.cse.iitd.ac.in/~naveen/courses/CSL851/lec7.pdf
  18. https://inria.hal.science/hal-01798795/document
  19. https://www.sciencedirect.com/science/article/abs/pii/S0012365X22004691
  20. https://www.math.ucsd.edu/~fan/mypaps/fanpap/85docn.PDF
  21. https://arxiv.org/pdf/2402.08538
  22. https://www.whitman.edu/mathematics/cgt_online/book/section05.02.html
  23. https://www.math.stonybrook.edu/~sorin/118/E2info.pdf
  24. https://math.stackexchange.com/questions/624220/eulerian-graph-has-no-bridges
  25. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-2-4.pdf
  26. https://quizlet.com/explanations/questions/a-can-a-graph-with-an-euler-cycle-have-a-bridge-an-edge-whose-removal-disconnects-the-graph-prove-or-give-a-counterexample-b-give-an-example-1b73382c-ecf62004-f63c-48cf-81b8-4411a8d8a578
Add your contribution
Related Hubs
User Avatar
No comments yet.