how to calculate how many pairwise non-isomorphic graphs can be constructed from graph by adding one new edge. For example graph with 4 vertices.
As mentioned in the comments, a set of graphs (G) is pairwise non-isomorphic if for any pair of graphs (g, h) in G, g is not isomorphic to h.
You have a couple of options (at least). Lets call the starting set of graphs the base set and adding an edge to a graph an augmentation:
- Add a new edge everywhere you can for each graph in the base set then filter out duplicates
- Determine the symmetries of the graphs in the base set and add new edges to one representative of each attachment point
The first of these options is the easiest for small base sets (equivalently, for graphs on small numbers of vertices). For example, take the square - you can add a new edge to each of the vertices to get a graph on 5 vertices ... but of course all of these augmentations will be pairwise isomorphic.
The difficulty with the second approach is that augmenting different base graphs can lead to the same output graph. For example see this pair of augmentations:
Of course, you can follow the same procedure as in the first approach of simply filtering out these duplicates, but this becomes computationally expensive for larger graphs. A far better approach is described by Brendan McKay of canonical path augmentation. This involves rejecting augmentations that would lead to non-canonical child graphs, but it's a little long for this answer and described better elsewhere.