# Graph Theory: Simple Graph

Show that, if $$G$$ is simple, the edge graph of $$G$$ has $$E(G)$$ vertices and $$\sum {d(v) \choose 2}$$ edges.

Observe that a graph is called simple if it has no multiple edges (this is, edges whose start and end points are the same, in other words, parallel edges) and no loops (this is, an edge that goes from a point to itself) being connected or not, even though it can have cycles.

I know that an edge graph of a graph $$G$$ is the graph with vertex set $$E(G)$$ in which $$2$$ vertices are joined if and only if they are adjacent edges in $$G$$. So, logically, it seems pretty clear that if $$G$$ is simple, the edge graph has $$E(G)$$ vertices. However, I just began this course so I am not too familiar with how to prove things yet. Also, I have no idea how to prove the second part of this. Any help would be great, thanks.

• I didn't comprehend how you got this formula for the number of edges. Nov 3, 2021 at 11:36

Hint: to be specific, imagine a vertex in $G$ of degree $4$. Every pair of edges (in $G$) incident on the vertex will give an edge in $E(G)$. How many such pairs are there?

To prove this statement you just need to count the edges in the edge graph.

An edge exists in the edge graph if there are two edges adjacent in the original graph. The two edges would have to share a vertex. Instead of looking at edges, lets look at the vertices.

For a vertex, $d(v)$ is the number of edges incident to that vertex. Any two edges incident to the same vertex are adjacent edges. Therefore there are $\binom{d(v)}{2}$ adjacent edges per vertex. Thus vertex $v$ represents that many edges in the edge graph.

Since the graph is simple, two edges will not be adjacent at more than one vertex. Otherwise it would be a double edge. Thus each edge in the edge graph is only counted once by our method.

So there are $\sum_{v} \binom{d(v)}{2}$ edges in the edge graph.

Understand this in a very simple way. If you have something say simply a line then that line would have two vertices each with degree 1 and a single edge.So, if you sum the degrees of all the vertices then that becomes 2 which is twice the number of edges. So the number of edges is equal to sum of degrees of all the vertices divided by 2. Now, have a general idea that in a graph the degree of a vertex is the number of edges adjacent to it and each edge contributes 1 to the degree of the vertex it is attached to. So, any edge will actually contribute a total degree of 2 because of being attached to two vertices. So, now you can understand how the total number of edges is equal to half the sum of the degrees of all the vertices.