[Graph theory] Formula for the size of a line graph

[dbh2ppa]

Homework Statement

Let G be a graph of order n and size m.
V(G)={v₁,v₂,...,v_n} and deg(v_i)=r_i.
Find a formula for the size of the line graph L(G) in terms of n, m, and r_i.

Homework Equations

The http://en.wikipedia.org/wiki/Line_graph" L(G) is the graph such that every vertex in L(G) corresponds to an edge in G, and two vertices in L(G) are adjacent iff the corresponding edges in G share a vertex.

The Attempt at a Solution

I know that the degree of any w in V(L(G)), when w is equivalent to some edge (v_a,v_b) in G, is (r_a-1)+(r_b-1), that is to say r_a+r_b-2.
The size of L(G) would be (with it's vertices labeled from 1 to m).
$$\frac{\sum_{i=1}^{m} r_{a_{i}}+r_{b_{i}}-2}{2}$$
Where v_ai and v_bi are the vertices of the edge in G corresponding to w_i in L(G). This, however, seems to be the least elegant solution possible. Is there a better solution? Are there any errors in the one I wrote? (I really am not sure about it).

 

[mighty2000]

Thank you for your post. I am happy to assist you in finding a formula for the size of the line graph L(G) in terms of n, m, and ri.

First, let's start by defining some terms. The order of a graph is the number of vertices in the graph, denoted by n. The size of a graph is the number of edges in the graph, denoted by m. The degree of a vertex is the number of edges incident to that vertex, denoted by ri.

Now, let's take a closer look at the line graph L(G). As you correctly stated, L(G) is a graph where each vertex corresponds to an edge in G and two vertices in L(G) are adjacent if the corresponding edges in G share a vertex.

To find a formula for the size of L(G), we can start by considering the number of vertices in L(G). Since each vertex in L(G) corresponds to an edge in G, and G has m edges, L(G) will have m vertices.

Next, we can consider the degree of each vertex in L(G). As you mentioned, the degree of a vertex w in L(G) is equal to (ra-1)+(rb-1) where ra and rb are the degrees of the vertices in G that correspond to the edge represented by w in L(G).

Therefore, the total sum of degrees in L(G) is given by:

\sum_{i=1}^{m} [(ra-1)+(rb-1)] = 2m-2m = 0

Since the sum of degrees in a graph is always equal to twice the number of edges, we can conclude that L(G) has 2m edges.

In conclusion, the size of L(G) is equal to 2m, or simply twice the size of G. Therefore, the formula for the size of L(G) in terms of n, m, and ri is:

|L(G)| = 2m

I hope this helps you understand the size of the line graph L(G) better. Let me know if you have any further questions or if you need clarification.