Реберный граф графа (line graph) G=(X, U) - граф U(G)=(U, Е) называются реберным, если каждой вершине uU(G) сопоставлено ребро uU и две вершины в U(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.