b'\n_START_ARTICLE_\nObseg (teorija grafov)\n_START_PARAGRAPH_\nObseg v teoriji grafov pomeni dva pojma. Notranji obseg (angle\xc5\xa1ko girth) grafa je dol\xc5\xbeina njegovega najkraj\xc5\xa1ega cikla. \xc4\x8ce graf ne vsebuje ciklov (je acikli\xc4\x8dni graf), je njegov notranji obseg po definiciji enak neskon\xc4\x8dnosti. Notranji obseg 4-cikla (kvadrata) je 4. Notranji obseg mre\xc5\xbee je tudi enak 4, trikotni\xc5\xa1ke mre\xc5\xbee pa enak 3. Graf z notranjih obsegom ve\xc4\x8djim od 3 nima trikotnikov. Zunanji obseg (angle\xc5\xa1ko circumference) grafa je dol\xc5\xbeina njegovega najdalj\xc5\xa1ega cikla. Obsega predstavljata invarianti grafa.\n_START_SECTION_\nKletke\n_START_PARAGRAPH_\nKubi\xc4\x8dni graf (vse njegove to\xc4\x8dke imajo stopnjo 3) z notranjim obsegom , ki je majhen kolikor je mogo\xc4\x8de, je znan kot -kletka (ali kot (3,g)-kletka). Petersenov graf je edina 5-kletka (je najmanj\xc5\xa1i kubi\xc4\x8dni graf z notranjim obsegom 5), Heawoodov graf je edina 6-kletka, McGeejev graf je edina 7-kletka, Tuttejeva osmera kletka pa je edina 8-kletka. Za dani notranji obseg lahko obstaja ve\xc4\x8d kletk. Obstajajo na primer tri neizomorfne 10-kletke, vsaka s 70-timi to\xc4\x8dkami: Balabanova 10-kletka, Harriesov graf in Harries-Wongov graf.\n_START_SECTION_\nNotranji obseg in barvanje grafa\n_START_PARAGRAPH_\nZa poljubni pozitivni celi \xc5\xa1tevili g in \xcf\x87 obstaja graf z notranjim obsegom vsaj g in kromati\xc4\x8dnim \xc5\xa1tevilom vsaj \xcf\x87. Gr\xc3\xb6tzschev graf na primer nima trikotnikov, njegovo kromati\xc4\x8dno \xc5\xa1tevilo je enako 4. S ponavljanjem konstrukcije Mycielskega lahko iz Gr\xc3\xb6tzschevega grafa dobimo grafe brez trikotnikov s poljubno velikim kromati\xc4\x8dnim \xc5\xa1tevilom. Paul Erd\xc5\x91s je prvi dokazal splo\xc5\xa1ni rezultat s pomo\xc4\x8djo verjetnostne metode. Pokazal je, da naklju\xc4\x8dni graf na n to\xc4\x8dkah, ki je nastal z neodvisno izbiro vsake povezave z verjetnostjo n, ima, \xc4\x8de verjetnost te\xc5\xbei k 1, ko gre n k neskon\xc4\x8dnosti, najve\xc4\x8d n/2 ciklov dol\xc5\xbeine g ali manj, vendar nima neodvisne mno\xc5\xbeice velikosti n/2k. \xc4\x8ce odstranimo eno to\xc4\x8dko iz vsakega kratkega cikla, zato dobimo manj\xc5\xa1i graf z notranjim obsegom ve\xc4\x8djim od g, v katerem mora biti vsak barvni razred barvanja majhen in zaradi tega potrebuje vsaj k barv v vsakem barvanju.\n_START_SECTION_\nPosplo\xc5\xa1itve\n_START_PARAGRAPH_\nLihi notranji obseg in sodi notranji obseg grafa sta dol\xc5\xbeini najkraj\xc5\xa1ega lihega cikla in najkraj\xc5\xa1ega sodega cikla._NEWLINE_Prek najmanj\xc5\xa1e dol\xc5\xbeine netrivialnega cikla notranji obseg dovoljuje naravne posplo\xc5\xa1itve 1-sistol ali sistol vi\xc5\xa1jih redov v sistoli\xc4\x8dni geometriji.'