CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
venkysmarty
venkysmarty

Reputation: 11431

Graph max number of edges and isomorphic

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 is accounted for 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 isomorphism problem because there are V! possible ways to label the vertices.

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

Upvotes: 0

Views: 173

Answers (1)

Codor
Codor

Reputation: 17605

  1. For |V|=3, the maximum number of edges is 3, which would define the complete graph on 3 vertices. To illustrate the proof, there are 3*3=9 ordered pairs of vertices. Out of these, 3 are loops, leaving 6 ordered pairs. In these 6 ordered pairs, there are only 3 consisting out of 2 distict vertices, leaving 3 remaining edges in total. In terms of data structures, this can be imagined as follows. The incidence structure of a loop-free undirected graph can be modelled by using an n times n binary matrix which has all zeros below the main diagonal and all zeros on the main diagonal, leaving n(n-1)/2 entries potentially nonzero (namely the entries above the main diagonal).

  2. Given the complete graph on n vertices, each rearrangement of the vertices yields an isomorphic graph, which means that there are potentially n! (the number of permutations of n objects) isomorphic graphs to any given graph. Of course, non-complete graphs have less possibilities to rearrange the vertices to yield an isomorphic graph.

Upvotes: 1

Related Questions