# How to determine if a graph is two-connected?

3 views (last 30 days)
Ephraim Bryski on 11 Jan 2021
Commented: Christine Tobler on 12 Jan 2021
Hi. I have a graph in MATLAB and I would like to determine if it is two-connected. I would also like to have the graphs which it can be separated into as outputs. Is there a way of doing this efficiently in MATLAB, either using built-in functionality, or writing code? Thanks!

Christine Tobler on 11 Jan 2021
The biconncomp function will split the edges of a graph into its biconnected components. If the output of biconncomp is a vector of all ones, that graph is two-connected.
Otherwise, here's some code that will extract each biconnected component as an individual graph as follows:
s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G);
bins = biconncomp(G);
for binNr = 1:max(bins)
st = G.Edges.EndNodes;
Gbin = subgraph(G, unique(st(bins == binNr, :)));
figure;
plot(Gbin)
end
Keep in mind: For a graph without node names in MATLAB, nodes are numbered through 1, 2, ..., [number of nodes]. This means that the subgraph command can assign a new node index (e.g., if G has three nodes, subgraph(G, [1 3]) will return a graph where the previous node 3 is now node 2). You can avoid this by using node names.
Christine Tobler on 12 Jan 2021
If a graph is 3- or 4- connected, this means it is also two-connected (biconnected). The biconncomp function only answer the question of whether a graph is two-connected or how it can be split into biconnected components.
MATLAB doesn't have functionality for computing k-connectivity except for k=1 (conncomp) and k=2 (biconncomp). For the 3-connected case I think you're looking for, a quick wikipedia search suggests you might need to look at the concept of SPQR trees. An algorithm is described on that page, with reference to papers for details.

R2020b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!