گراف خط

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

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

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

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

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

یال مذکور تنها با این $Z(r-1)$ یال رأس مشترک دارد و در این یال رأس گراف $L(g)$ است که به $Z(r-1)$ رأس دیگر متصل است.

پس $L(G)$ یک گراف $Zr-Z$ منتظم است.

نگارخانه

Kenneth H, Rosen (1998). "graphs". Discrete Mathematics and its Applications. SIGS Reference Library (in English). William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. {{cite book}}: تاریخ وارد شده در |بازبینی= را بررسی کنید (کمک)

[daneshnameh.roshd.ir daneshnameh.roshd.ir]. {{cite web}}: مقدار |نشانی= را بررسی کنید (کمک); پارامتر |عنوان= یا |title= ناموجود یا خالی (کمک)