Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Biconnected graph
open-in-new
<h2 id="definition">Definition</h2> <p>A biconnected <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges). </p><p>A biconnected <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> is one such that for any two vertices <i>v</i> and <i>w</i> there are two directed paths from <i>v</i> to <i>w</i> which have no vertices in common other than <i>v</i> and <i>w</i>. </p> <h2 id="examples">Examples</h2> Nonseparable (or 2-connected) graphs (or blocks) with n nodes (sequence A002218 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)<table><tbody><tr><th>Vertices</th><th>Number of Possibilities</th></tr><tr><th>1</th><td>0</td></tr><tr><th>2</th><td>1</td></tr><tr><th>3</th><td>1</td></tr><tr><th>4</th><td>3</td></tr><tr><th>5</th><td>10</td></tr><tr><th>6</th><td>56</td></tr><tr><th>7</th><td>468</td></tr><tr><th>8</th><td>7123</td></tr><tr><th>9</th><td>194066</td></tr><tr><th>10</th><td>9743542</td></tr><tr><th>11</th><td>900969091</td></tr><tr><th>12</th><td>153620333545</td></tr><tr><th>13</th><td>48432939150704</td></tr><tr><th>14</th><td>28361824488394169</td></tr><tr><th>15</th><td>30995890806033380784</td></tr><tr><th>16</th><td>63501635429109597504951</td></tr><tr><th>17</th><td>244852079292073376010411280</td></tr><tr><th>18</th><td>1783160594069429925952824734641</td></tr><tr><th>19</th><td>24603887051350945867492816663958981</td></tr></tbody></table> <h2 id="structure-of-2-connected-graphs">Structure of 2-connected graphs</h2> <p>Every 2-connected graph can be constructed inductively by adding <a href="/facts/Path_(graph_theory)/WMsq21Nf">paths</a> to a <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a> (Diestel 2016, p. 59). </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Biconnected_component/Y4221AkA">Biconnected component</a></li></ul> <ul><li>Eric W. Weisstein. "Biconnected Graph." From MathWorld—A Wolfram Web Resource. <a href="http://mathworld.wolfram.com/BiconnectedGraph.html">http://mathworld.wolfram.com/BiconnectedGraph.html</a></li> <li>Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: <a href="https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html">https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html</a></li> <li><a href="/facts/Reinhard_Diestel/Fzv2bX8x">Diestel, Reinhard</a> (2016), <a href="https://diestel-graph-theory.com/index.html"><i>Graph Theory</i></a> (5th ed.), Berlin, New York: Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-662-53621-6.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://code.google.com/p/jbpt/">The tree of the biconnected components Java implementation</a> in the jBPT library (see BCTree class).</li></ul>