# A graph with $V$ vertices has at most $V(V-1)/2$ Edges

A graph with $V$ vertices has at most $V(V-1)/2$ Edges

Proof: The total of $V^2$ possible pairs of vertices include $V$ self-loops and accounts twice for each edge between distinct vertices, so the number of edges is at most $(V^2 -V)/2 = V(V-1)/2$.

Question 1: Request your help in understanding above property with $V$ equal to $3$.

Isomorphic: Two graphs are isomorphic if we can change the vertex labels on one graph to make its set of edges identical to the other. It is challenging to solve isomorphic problem because there are $V!$ possible ways to label the vertices.

Question 2: Request your help on how the author came up with $V!$ possible ways.

• This question has been cross-posted between math and SO. I've edited it on one (and wondered why the edits didn't show up on the other!). Since it has been answered here, I'll make the same edits. – gilleain Jul 6 '15 at 14:59
• What's special about $V = 3$? – anomaly Jul 6 '15 at 15:11
• It may help to notice that $V(V-1)/2 = \binom{V}{2}$ ($V$ choose $2$). – Najib Idrissi Jul 6 '15 at 15:15

Question 1: You just have a $3$-cycle. This is because if you add any other edge, then this edge would either be a self-loop or a multiple edge. Often times in graph theory authors specify the use of simple undirected graphs unless otherwise noted. A simple undirected graph has no self-loops or multiple edges.
Question 2: You get $V!$ because you first choose a vertex to label. You have $V$ possible ways to label this vertex. Then choose another vertex to label. You now have $V-1$ possible ways to label this vertex since you already labeled one vertex. And so on. So you get $$V(V-1) \cdots (2)(1) = V!.$$