The similarity between two undirected graphs $G_1$ and $G_2$ that have the same $n$ vertices can be defined using:

$$ S(G_1,G_2) = \frac {\sum_i\min(\deg(v_i \in G_1), \deg(v_i \in G_2))} {2 \times \max(|G_1|,|G_2|)} $$

where $\deg(v \in G)$ indicates the degree of a vertex $v$ in graph $G$ and $|G|$ indicates the number of edges in $G$. If $S(G_1, G_2) = 1$, are the two graphs equivalent?

  • 3
    $\begingroup$ Is there some standard metric for similarity you are referring to? Can you provide a definition and/or reference? $\endgroup$
    – GeoMatt22
    Sep 26, 2016 at 2:17
  • $\begingroup$ Similarity of two undirected graphs having the same n vertices is 1 $\endgroup$
    – Mk47
    Sep 26, 2016 at 4:01
  • $\begingroup$ If that is the definition, then you would seem to have answered your own question? However your statement seems like an odd definition of graph similarity, when it only has to do with vertex sets. Typically a graph would be defined as $\{E,V\}$, which includes both a vertex set $V$ as well as an edge-set $E\subset V\times V$ (at a minimum, i.e. for an unweighted graph). $\endgroup$
    – GeoMatt22
    Sep 26, 2016 at 14:03

1 Answer 1


Unfortunately, graph isomorphism is a harder problem then just matching vertex degrees, as this figure demonstrates.


Both are undirected graphs on the same six vertices, labeled "1" through "6". The vertex degrees on both are the same, vertex by vertex: one vertex ("1") has degree 5, two ("3" and "6") have degree 2, and three have degree 3. Therefore your similarity metric equals $1$.

Note, however, that the three degree-3 vertices (labeled "2", "4", and "5") form a triangle at the left but not at the right. Therefore the two graphs are not isomorphic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.