A gráfelmélet területén egy irányítatlan G gráfhoz tartozó élgráf egy olyan L(G) gráf, amely a G gráf élei közötti szomszédsági viszonyokat reprezentálja. Röviden élgráf az a gráf, amiben a csúcspontok az eredeti gráf élei, és két csúcs akkor van összekötve, ha az eredeti gráfban a két élnek volt közös végpontja. Maga az élgráf (line graph) kifejezés -ból jön, bár a konstrukciót előtte és is használta.Hemminger,Beineke (1978),p.273 Az élgráf egyéb megnevezései közé tartozik a covering graph (burkológráf), a derivative (származtatott gráf), az edge-to-vertex dual (él–csúcs-duális), a conjugate (konjugált gráf), a representative graph (reprezentatív gráf) és a ϑ-obrazom,Hemminger,Beineke (1978), p.273 továbbá az edge graph (élgráf), az interchange graph (cseregráf), az adjoint graph és a derived graph., p. 71.
igazolta, hogy egy kivételes esettől eltekintve az összefüggő gráfok szerkezete visszanyerhető élgráfjuk ismeretében. Az élgráfok számos tulajdonsága közvetlenül az eredeti gráf csúcsainak élekké konvertálására vezethető vissza, és Whitney tétele értelmében ez az átalakítás visszirányban is végrehajtható. Az élgráfok karommentesek, a páros gráfok élgráfjai pedig perfekt gráfok. Az élgráfokat kilenc tiltott részgráf jellemzi, és lineáris idő alatt felismerhetők.
Az élgráfok számos általánosítását tanulmányozták már, köztük az élgráfok élgráfjait, a multigráfok élgráfjait, a hipergráfok élgráfjait és a súlyozott gráfok élgráfjait.
Formális definíció Vegyünk egy G gráfot, ekkor L(G) élgráfja olyan gráf, amire a következők teljesülnek: minden L(G)-ben szereplő csúcs megfelel egy G-ben lévő élnek; két csúcs L(G)-ben akkor és csak akkor szomszédos, ha a nekik megfelelő éleknek van közös végpontjuk G-ben. Tehát az élgráf G éleinek metszetgráfja , ami minden élet két végpontjával reprezentál.
Példa A következő ábrákon egy gráf látható (bal oldal, kék csúcsok) a hozzá tartozó élgráfjával (jobb oldal, zöld csúcsok). Az élgráf minden csúcsa meg van címkézve az eredeti gráf hozzá tartozó éle szerint. Például a jobb oldali 1,3 címkéjű zöld csúcs a bal oldalon az 1-es és 3-as kék színű csúcsokat összekötő élet jelképezi. A zöld 1,3 csúcs szomszédos három másik zöld csúccsal: az 1,4-gyel és 1,2-vel (mindkettő az 1-es csúcsból kiinduló él) és a 4,3 (a 3 végű él a kék gráfban).
Tulajdonságok Az alapját képező gráf tulajdonságainak változásai A G gráf az éleinek szomszédosságán alapuló tulajdonságai átalakulnak az L(G) csúcsok szomszédosságán alapuló tulajdonságaiba. Például G egy párosítása olyan élek halmaza, melyek közül páronként egyik sem szomszédos; ez L(G)-ben megfelel csúcsok olyan halmazának, melyben semelyik két csúcs nem szomszédos, tehát a csúcsok független halmazt alkotnak.
Így aztán: Egy összefüggő gráf élgráfja is összefüggő. Ha G összefüggő, tartalmaz bármely két élét összekötő sétát, ami az L(G) élgráf bármely két csúcsát összekötő sétává alakul. Azonban található olyan, izolált csúcsokkal rendelkező G gráf, aminek élgráfja mégis összefüggő.Az izolált csúcsok vizsgálatának szükségességét mondja ki, p. 32. Egy élgráfnak akkor és csak akkor létezik elvágó pontja (artikulációs pontja), ha az eredeti gráf tartalmaz olyan elválasztó élt (hidat), melynek egyik végpontja sem elsőfokú. Egy n csúccsal és m éllel rendelkező G gráfhoz tartozó L(G) élgráf csúcsainak száma m, éleinek száma pedig G csúcsai fokszámának négyzetösszegének fele mínusz m., Theorem 8.1, p. 72. Egy élgráf maximális független halmaza az eredeti gráf maximális párosításának feleltethető meg. Mivel a maximális párosítások polinomiális időben megtalálhatók, ugyanez a helyzet az élgráfok maximális független halmazaival is, annak ellenére, hogy általános gráfoknál a maximális független halmaz keresése nehezebb probléma. A G gráf élkromatikus száma megegyezik L(G) élgráfjának (csúcs)kromatikus számával.. Also in free online edition, Chapter 5 ("Colouring"), p. 118. Egy éltranzitív gráf élgráfja csúcstranzitív. Ennek a tulajdonságnak a segítségével generálhatók a Petersen-gráfhoz hasonló olyan gráfcsaládok, melyek csúcstranzitívak, de nem Cayley-gráfok: ha a G éltranzitív gráf legalább öt csúcsból áll, nem páros és vannak páratlan fokszámú csúcsai, akkor L(G) egy csúcstranzitív nem-Cayley-gráf.. Lauri és Scapellato szerint ez az eredmény Mark Watkins érdeme. Ha G gráfnak van Euler-köre, tehát olyan összefüggő gráf, aminek minden csúcsából páros számú él indul ki, akkor G élgráfja Hamilton-gráf. Azonban nem minden Hamilton-utat tartalmazó élgráf származtatható Euler-kört tartalmazó gráfból; minden Hamilton-utat tartalmazó gráf élgráfja is tartalmaz Hamilton-utat, függetlenül attól, hogy Euler-kört is tartalmazott-e az eredeti gráf., Theorem 8.8, p. 80. Ha két gráf izomorf, élgráfjaik is izomorfak. Whitney izomorfizmustétele szerint a fordítottja is igaz, egyetlen gráf kivételével. A komplex hálózatok elméletében egy véletlen hálózat élgráfja megőrzi a hálózat számos tulajdonságát, köztük a kisvilág-tulajdonságot (bármely két csúcspár közötti rövid út létezése) és a fokszámeloszlás alakjátRamezanpour,Karimipour,Mashagh (2003) megfigyelése szerint a komplex hálózatban csúcsklaszterek keresésére alkalmazott módszerek használhatól az élgráf élklaszterezésére is.
Whitney izomorfizmustétele bélyegkép|120px|gyémántgráf, kivétel az erős Whitney-tétel alól Ha két összefüggő gráf élgráfjai izomorfak, az eredeti gráfok is izomorfak, kivéve a K3 háromszöggráf és a K1,3 csillaggráf esetét, melyek élgráfjai izomorfak, de ők maguk nem azok.; ; , Theorem 8.3, p. 72. Harary megadja a tétel egyszerűsített bizonyítását itt: .
A K3 és K1,3 esetén kívül van néhány kivételes, kis méretű gráf, melyek élgráfja nagyobb szimmetriát mutat az eredeti gráfnál. Például a K1,1,2 gyémántgráf (két, közös éllel rendelkező háromszög) négy gráfautomorfizmussal rendelkezik, de élgráfja, a K1,2,2 nyolccal. A gyémántgráf illusztrációján látható, hogy a gráf 90 fokkal történő elforgatása nem szimmetriája a gráfnak, az élgráfjának azonban igen. Az ilyen kivételes esetek azonban legfeljebb négy csúcsszámú gráfoknál fordulnak elő. Whitney izomorfizmus-tételének erős változata szerint négy csúcsnál többet tartalmazó összefüggő gráfok esetében 1:1 megfeleltetés létezik a gráfok izomorfizmusai és élgráfjaik izomorfizmusai között.; .
A Whitney-izomorfizmustételnek léteznek multigráfok élgráfjaira vonatkozó változatai, de azok komplikáltabbak.
Erősen reguláris élgráfok és élperfekt gráfok bélyegkép|240px|Egy élperfekt gráf. Minden kétszeresen összefüggő komponens éleit feketére színeztük, ha a komponens páros, kékre, ha a komponens tetraéder és pirosra, ha a komponens háromszögekből álló könyv. A Kn teljes gráf élgráfja a trianguláris gráf vagy J(n,2) Johnson-gráf, ami a KGn,2 Kneser-gráf komplementere. A trianguláris gráfokat jellemzi spektrumuk, kivéve az n = 8 esetet.. Lásd különösen itt: Proposition 8, p. 262. Jellemezhetők úgy is (ismét a K8 kivételével) mint olyan erősen reguláris gráfok, melynek paraméterei srg(n(n − 1)/2, 2(n − 2), n − 2, 4)., Theorem 8.6, p. 79. Harary credits this result to independent papers by L. C. Chang (1959) and A. J. Hoffman (1960). A három erősen reguláris gráfot, aminek paraméterei és spektruma megegyezik az L(K8) gráffal Chang-gráfoknak nevezik, melyek az L(K8)-ból gráfkapcsolással állíthatók elő.
A páros gráf élgráfja mindig perfekt gráf (lásd Kőnig-tétel). A páros gráfok élgráfjai fontos szerepet játszanak a perfekt gráfok vizsgálatában, felhasználták az erős perfektgráf-tétel bizonyítása során is.. See also . Az ilyen gráfok speciális esetei a bástyagráfok, melyek a teljes páros gráfok élgráfjai. A teljes gráfok élgráfjaihoz hasonlóan egyetlen kivétellel jellemzi őket csúcsaik, éleik, illetve a szomszédos és nem szomszédos csúcsokkal közös szomszédjaik száma. Az egyetlen kivételes eset az L(K4,4), aminek paraméterei a Shrikhande-gráffal egyeznek meg. Ha a páros gráf mindkét partíciójában ugyanannyi csúcs található, ezek az élgráfok szintén erősen regulárisak., Theorem 8.7, p. 79. Harary a teljes páros gráfok élgráfjainak jellemzését Moon and Hoffman-nak tulajdonítja. A két partícióban azonos számú csúcsok esetét korábban Shrikhande igazolta.
Általánosabban, ha L(G) perfekt gráf, G gráfot élperfekt gráfnak nevezzük. Az élperfekt gráfok pontosan azok a gráfok, melyek nem tartalmaznak páratlan hosszúságú, háromnál nagyobb egyszerű kört.; . Ezzel ekvivalens állítás, hogy egy gráf akkor és csak akkor élperfekt, ha minden kétszeresen összefüggő komponense vagy páros, vagy K4 (tetraéder) vagy egy K1,1,n teljes háromrészes gráf (közös élből kiinduló háromszögekből álló „könyv”).Maffray,1992 Minden élperfekt gráf egyben perfekt gráf is.Trotter,1977
Egyéb kapcsolódó gráfcsaládok Minden élgráf karommentes gráf, tehát olyan gráf, melynek nem feszített részgráfja a háromlevelű fa. Ahogy az a karommentes gráfokra általában is igaz, bármely összefüggő, páros számú éllel rendelkező L(G) élgráf teljes párosítással rendelkezik.. .
A fák élgráfjai karommentes blokkgráfok., Theorem 8.5, p. 78. Harary credits the result to Gary Chartrand. Ezek a gráfok szerepet játszanak az extremális gráfelmélet egy problémájának megoldásában; olyan gráf szerkesztésében, melynek csúcs- és élszáma adott, és melyben a legnagyobb feszített részfa a lehető legkisebb méretű..
Egy élgráf szomszédsági mátrixának sajátértékeinek nagysága legalább −2. Emiatt az ilyen szomszédsági mátrix sajátértékkel rendelkező gráfokat egyesek általánosított élgráfoknak tekintik.Cvetković,Rowlinson,Simić (2004)
Jellemzés és felismerés Klikkpartíció bélyegkép|280px|Élgráf klikkekre particionálása Bármely G gráf egy tetszőlegesen kiválasztott v csúcsa esetében a v-ből kiinduló élek megfelelnek az L(G) élgráf egy klikkjének. Az így kialakuló klikkek particionálják L(G) éleit. Minden L(G)-beli csúcs pontosan két klikkhez tartozik (a G-beli él két végpontjának megfelelő két klikkhez).
Az említett klikkekre való particionálás létezése alkalmas az élgráfok jellemzésére: Egy L gráf akkor és csak akkor az élgráfja valamely gráfnak vagy multigráfnak, ha lehetséges L-ben klikkek olyan gyűjteményét azonosítani (megengedve, hogy egyes klikkek egyetlen csúcsból álljanak), melyek L éleit úgy particionálják, hogy L minden csúcsa pontosan két klikkbe tartozzon., Theorem 8.4, p. 74, három ekvivalens jellemzést ad az élgráfokra: az élek klikkekbe való particionálását, a karommentességet és páratlan gyémántgráf-mentességet, valamint Beineke kilenc tiltott részgráfját. Gráf (és nem multigráf) élgráfjáról van szó, ha a klikkek halmaza teljesíti még azt a feltételt is, hogy L semelyik két csúcsa nem tartozik ugyanabba a két klikkbe. Egy ilyen klikkcsalád segítségével úgy nyerhető vissza L-ből az eredeti G gráf, hogy minden klikkhez egy csúcsot hozunk létre G-ben, majd minden L-beli csúcshoz egy olyan élet, melynek végpontjai a csúcsot tartalmazó két L-beli klikk. A Whitney-féle izomorfizmustétel erős változata alapján, ha G-nek négynél több csúcsa van, csak egyetlen ilyen partíció létezhet.
Tekintsük az alábbi gráfot, mely a fenti jellemzők alapján nem egy élgráf: 100px A példabeli gráf középső, negyedfokú csúcsából felfelé, balra és jobbra induló élek nem osztoznak közös klikken. Ezért bármely, a gráf éleit klikkekbe osztó particionálás legalább egy klikket rendelne ehhez a három élhez, melyek mind a középső csúcsban metszenék egymást, megsértve a követelményt, hogy minden csúcsnak pontosan két klikkbe kell tartoznia. Tehát a fenti gráf nem élgráf.
Tiltott részgráfok bélyegkép|300px|A kilenc minimális nem-élgráf, az élgráfok Beineke-féle tiltottrészgráf-karakterizációjából. Egy gráf akkor és csak akkor élgráf, ha egyet sem tartalmaz feszített részgráfként az ábrán látható gráfokból.