# If two graphs have similarity equal to 1 are their vertexes and edges equal?

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?

• Is there some standard metric for similarity you are referring to? Can you provide a definition and/or reference? – GeoMatt22 Sep 26 '16 at 2:17
• Similarity of two undirected graphs having the same n vertices is 1 – Mk47 Sep 26 '16 at 4:01
• 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). – GeoMatt22 Sep 26 '16 at 14:03

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$.