Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.

share|cite|improve this question

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?

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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