connected subgraphs after deletion links

Hi there I have a graph with 7 nodes and 14 edges. i want to know how many connected sub graphs will creates if i delete 'n' links ? for example if i delete 0 links i have 1 sub graph ( main graph) if i delete 1 link i have 14 sub graphs (because i have 14 node and if i remove one of them the graph is still connected). Please Help me with this issue

Answer 1

[Sim]

The question is not very clear, but maybe you can use my example to get what you need:

% define edges
s = [1 1 2 3 4 5 6 7 8 9 9 10 11];
t = [2 7 3 4 5 6 7 8 9 10 12 11 12];

% add nodes coordinates (to make the example clearer)
nodes_coord = [
    0.5 1.5
    0 1
    1 1
    1.5 2
    1.5 2.5
    1 3 
    0 2
    0.5 4
    1.5 5
    3 4
    3 2
    2 3
    ]; 

% add nodes names (to make the example clearer)
node_names = cellstr(num2str((1 : 12)'));
% alternatively: node_names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L'}

% graph G
G = graph(s,t,[],node_names);

% plot
h = plot(G,'XData',nodes_coord(:,1),'YData', nodes_coord(:,2),'linewidth',2,'MarkerSize',2);
h.NodeLabel = [];
text(nodes_coord(:,1), nodes_coord(:,2), node_names, 'FontSize',15, 'FontWeight','bold', ...
    'HorizontalAlignment','left', 'VerticalAlignment','top');
set(gca,'Fontsize',15,'FontWeight','Bold','LineWidth',2, 'box','on');

% connected graph components 
[bin,binsize] = conncomp(G)

% results (figure and relative connected graph components)

bin =

     1     1     1     1     1     1     1     1     1     1     1     1


binsize =

    12

Now, we remove simultaneously two edges and let's see what we get:

% remove edges [1 2] and [8 9]
s_remove = [1 8];
t_remove = [2 9];

% graph G without edges [1 2] and [8 9]
Grmedge = rmedge(G,s_remove,t_remove)

% plot
figure
h = plot(Grmedge,'XData',nodes_coord(:,1),'YData', nodes_coord(:,2),'linewidth',2,'MarkerSize',2);
h.NodeLabel = [];
text(nodes_coord(:,1), nodes_coord(:,2), node_names, 'FontSize',15, 'FontWeight','bold', ...
    'HorizontalAlignment','left', 'VerticalAlignment','top');
set(gca,'Fontsize',15,'FontWeight','Bold','LineWidth',2, 'box','on');

% connected components 
[bin,binsize] = conncomp(Grmedge)

% results (figure and relative connected graph components)

bin =

     1     1     1     1     1     1     1     1     2     2     2     2


binsize =

     8     4