گراف خط



گراف خط 
گراف غیر تهی G را در نظر بگیرید. اگر به جای هر یال G راأسی در نظر بگیریم و دو رأس را به هم متصل می‌کنیم.

در صورتی که یال‌های متناظر آن دو رأس در G در یک رأس از G با هم مشترک باشند.

گراف حاصل را با  نشان داده و آن را گراف خط می‌نامیم.

قضیه: اگر G و  منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه  می‌باشد.

اثبات: هر یال گراف G به دو رأس ختم می‌شود که به هر یک از این رأس‌ها به جز یال مذکور ،  یال دیگر وارد می‌شوند.

یال مذکور تنها با این  یال رأس مشترک دارد و در این یال رأس گراف  است که به  رأس دیگر متصل است.

پس  یک گراف  منتظم است.

نگارخانه

منابع 

 

خانواده‌های گراف
رده‌های تقاطعی گراف‌ها
عملیات گراف