گراف خط

گراف غیر تهی G را در نظر بگیرید. اگر به جای هر یال G راأسی در نظر بگیریم و دو رأس را به هم متصل می کنیم.
در صورتی که یال های متناظر آن دو رأس در G در یک رأس از G با هم مشترک باشند.
گراف حاصل را با L ( G ) {\displaystyle L(G)}   نشان داده و آن را گراف خط می نامیم.
قضیه: اگر G و − r {\displaystyle -r}   منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه 2 ( r − 1 ) {\displaystyle 2(r-1)}   می باشد.