Let G be a graph with vertex set V and edge set E. The line graph of G, denoted by
L(G), has E as its vertex set, where two vertices in L(G) are adjacent in L(G) if and only
if the corresponding edges in G are adjacent. Line graphs, a special type of graphs, share
many structure properties of general graphs: Cai and Corneil (1992) proved that the cycle
double conjecture holds for all 2-edge-connected graphs if and only if it holds for all 2-edge-
connected line graphs. We (Chen, H.-J. Lai and H.Y. Lai, 2001) proved that to solve Tutte’s
flow conjectures in graphs, one only needs to prove the truth of these conjectures in line graphs.
In this talk, a reduction method on graphs and line graphs and its applications will be discussed.
We will present some new results on the structure of line graphs and results on the relationships
between the line graph of the reduction of a graph G and the reduction of the line graph L(G)
of the graph G.