I am reading about graph theory.

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.

  • $\begingroup$ 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. $\endgroup$ – gilleain Jul 6 '15 at 14:59
  • $\begingroup$ What's special about $V = 3$? $\endgroup$ – anomaly Jul 6 '15 at 15:11
  • $\begingroup$ It may help to notice that $V(V-1)/2 = \binom{V}{2}$ ($V$ choose $2$). $\endgroup$ – 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!.$$


The formula of half (V-squared minus V) comes from :

  1. V-squared pairs {(1, 1), (1, 2), (1, 3), ..., (V, 1), (V, 2), ..., (V, V)}.
  2. Minus the self-loops : {(1, 1), (2, 2), ..., (V, V)}

This is probably easiest to see if you draw a graph and fill in the associated adjacency matrix.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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