 Граф Пелі з дев'ятьма вершинами є локально лінійним. Один із шести трикутників виділено зеленим.
Локально лінійний граф — неорієнтований граф у якому кожне ребро  належить рівно одному трикутнику .Тобто для будь-якої вершини  будь-який окіл  має бути суміжним рівно ще одній вершині, сусідній з . Локально лінійні графи називають також локально парованими графами.

Прикладами локально лінійних графів є трикутні кактуси, реберні графи 3-регулярних графів без трикутників і прямий добуток дрібніших локально лінійних графів. Деякі кнезеровські графи, і деякі регулярні графи також локально лінійні.

Деякі локально лінійні графи мають майже квадратичну кількість ребер. Питання, наскільки щільні ці графи, може бути одним із формулювань задачі Ружі — Семереді. Відомі також найщільніші планарні графи, які можуть бути локально лінійними.

Побудови та приклади
 Кубооктаедр, планарний локально лінійний граф, який можна утворити як реберний граф куба або приклеюванням антипризм у внутрішню та зовнішню грані 4-циклу
Для локально лінійних графів відомі деякі побудови.

Приклеювання та добутки
Графи товаришування, утворені склеюванням разом набору трикутників в одній спільній вершині, локально лінійні. Це єдині скінченні графи, що мають сильнішу властивість, що будь-яка пара вершин (суміжних чи ні) мають рівно одну спільну сусідню вершину. Загальніше, будь-який трикутний кактус, граф, у якому всі прості цикли трикутні і всі пари простих циклів мають максимум одну спільну вершину, локально лінійні.

Нехай  і  — будь-які два локально лінійні графи. Виберемо трикутник з кожного з графів і склеїмо два графи разом, ототожнивши пари в цих трикутниках (це вид операції на графах суми за клікою). Тоді отриманий граф залишається локально лінійним.

Прямий добуток будь-яких двох локально лінійних графів залишається лінійно локальним, оскільки будь-які трикутники у добутку приходять з одного чи іншого множника. Наприклад, Граф Пелі з дев'ятьма вершинами (граф 3-3 дуопризми) є прямим добутком двох трикутників. Графи Геммінга  є добутками  трикутників, тому також локально лінійні.

Розмноження
Якщо граф  є 3-регулярним графом без трикутників, то реберний граф  є графом, утвореним перетворенням кожного ребра графа  на нову вершину і зв'язуванням двох вершин ребром у , якщо відповідні ребра графа  мають спільну кінцеву вершину. Ці графи є 4-регулярними та локально лінійними. Будь-який 4-регулярний локально-лінійний граф можна побудувати так. Наприклад, граф кубооктаедра можна утворити в цей спосіб як реберний граф куба, а граф Пелі з дев'ятьма вершинами є реберним графом комунального графа . Реберний граф графа Петерсена, інший граф цього типу, має властивість, аналогічну властивості кліток, що це найменший можливий граф, у якому найбільша кліка має три вершини, кожна вершина належить двом клікам, що не перетинаються, а найкоротший цикл із ребрами з різних клік має овжину 5.

Складніший процес розмноження застосовують до планарних графів. Нехай  — планарний граф, вкладений у площину так, що кожна грань чотирикутна, як у графа куба. Якщо приклеїти квадратну антипризму до грані графа , а потім видалити оригінальні ребра графа , отримаємо новий локально лінійний планарний граф. Кількість ребер і вершин результату можна обчислити за формулою Ейлера для многогранника: якщо  має  вершин, то він має  граней, а після заміни граней  антипризмами отримаємо  вершин та  ребер. Наприклад, з двох граней (внутрішньої та зовнішньої) 4-циклу в такий спосіб можна отримати кубооктаедр.

Алгебрична побудова
Кнезерів граф  має  вершин, що представляють -елементні підмножини -елементної множини. Дві вершини суміжні, якщо відповідні підмножини не перетинаються. Коли  результуючий граф локально лінійний, оскільки для кожних двох не перетинних -елементних підмножин є рівно одна -елементна підмножина (доповнення їх об'єднання), яка не перетинається з обома множинами. Отриманий локально лінійний граф має  вершин та  ребер. Наприклад, для  кнезерів граф  локально лінійний з 15 вершинами та 45 ребрами.

Локально лінійні графи можна побудувати з вільних від прогресій множин чисел. Нехай  — просте число і нехай  — підмножина чисел за модулем , таких, що ніякі три члени  не формують арифметичної прогресії за модулем . (Тобто  є  за модулем .) Тоді існує тричастковий граф, у якому кожна частка має  вершин,  ребер та кожне ребро належить єдиному трикутнику. Тоді, згідно з цією побудовою,  і число ребер дорівнює . Для побудови цього графа пронумеруємо вершини на кожній частці тричасткового графа від  до  і побудуємо трикутники вигляду  за модулем  для кожного  в інтервалі від  до  і кожного  з . Граф, утворений об'єднанням цих трикутників, має очікувану властивість, що будь-яке ребро належить єдиному трикутнику. Якби це було не так, існував би трикутник , де ,  і  належали б , що порушує припущення про відсутність арифметичних прогресій  в . Наприклад, з  і , результатом буде Граф Пелі з дев'ятьма вершинами.

Регулярні та сильно регулярні графи
Будь-який локально лінійний граф повинен мати парний степінь кожної вершини, оскільки ребро в кожній вершині можна розбити на пари для трикутників. Прямий добуток двох локально лінійних регулярних графів також локально лінійний і регулярний зі степенем, що дорівнює сумі ступенів множників. Отже, існують регулярні локально лінійні графи будь-якого парного степеня. -регулярні локально лінійні графи повинні мати принаймні  вершин, оскільки стільки є в трикутниках та сусідах. (Жодні дві вершини трикутника не можуть мати спільних сусідів без порушення локальної лінійності.) Регулярні графи з таким самим числом вершин можливі, тільки коли  1, 2, 3 або 5 і єдиним чином визначені для кожного з цих чотирьох випадків. Чотири регулярні графи, на яких досягається ця межа як функція від числа вершин, — це 2-регулярний трикутник  (3 вершини), 4-регулярний граф Пелі (9 вершин), 6-регулярний кнезерів граф  (15 вершин) та 10-регулярне доповнення графа Шлефлі (27 вершин). Останній у списку 10-регулярний граф із 27 вершинами також є графом перетинів 27 прямих на кубічній поверхні.

Сильно регулярний граф можна описати четвіркою параметрів , де  — число вершин,  — число інцидентних вершині ребер,  — число спільних сусідів для будь-якої суміжної пари вершин і  — число спільних сусідів для будь-якої несуміжної пари вершин. Коли , граф локально лінійний. Локально лінійні графи, як згадано вище, сильно регулярні, а їх параметри рівні

* трикутник (3,2,1,0),
* граф Пелі з дев'ятьма вершинами (9,4,1,2),
* кнезерів граф  (15,6,1,3),
* доповнення графа Шлефлі (27,10,1,5).

Інші локально лінійні строго регулярні графи:

* граф Брауера — Хемерса (81,20,1,6),
* граф Берлекемпа — ван Лінта — Зейделя (243,22,1,2),
* граф Косіденте — Пенттіли (378,52,1,8),
* граф Геймса (729,112,1,20).

Іншими потенційно правильними комбінаціями з  є (99,14,1,2) і (115,18,1,3), але не відомо, чи існують сильно регулярні графи з такими параметрами. Питання існування сильно регулярного графа з параметрами (99,14,1,2) відоме як задача Конвея про 99-вершинний граф і Джон Конвей запропонував приз 1000 доларів тому, хто її розв'яже.

Існує безліч локально лінійних дистанційно-регулярних графів степеня 4 або 6. Крім сильно регулярних графів однакового степеня, вони включають реберний граф графа Петерсена, граф Геммінга  і  графа Фостера.

Щільність
 Найщільніші можливі локально-лінійні планарні графи, утворені вклеюванням антипризми (червоні вершини і чорні ребра) в кожну квадратну грань планарного графа (сині вершини і пунктирні жовті ребра).
Одне з формулювань задачі Ружі — Семереді ставить питання про найбільшу кількість ребер у локально лінійному графі з  вершинами. Як довели Імре З. Ружа та Ендре Семереді, це найбільше число дорівнює , але також дорівнює  для будь-кого . Побудова локально лінійних графів із вільних від прогресій множин веде до найщільніших відомих локально лінійних графів із  ребрами.

Серед планарних графів найбільша кількість ребер у локально лінійному графі з  вершинами дорівнює . Граф кубооктаедра є першим у нескінченній послідовності поліедральних графів з  вершинами та  ребрами для , побудованими шляхом розширення квадратних граней  антипризми. Ці приклади показують, що ця верхня межа точна.

Примітки

