Reguljär graf

Inom grafteori är en reguljär graf en graf i vilken alla noder har samma grad eller valens. En reguljär riktad graf måste dessutom uppfylla kravet att ingraden är lika med utgraden. En reguljär graf med noder av graden k kallas en k-reguljär graf (eller helt enkelt en reguljär graf av grad k). De reguljära graferna med en grad upp till och med två är enkla att klassificera. En 0-reguljär graf består av fria noder, en 1-reguljär graf består av fria kanter och en 2-reguljär graf består av fria cykler och oändliga kedjor. En 3-reguljär graf kallas En "starkt reguljär graf" är en reguljär graf i vilken alla par av intilliggande noder har samma antal grann-noder gemensamma och varje par av icke intilligande noder har samma antal gemensamma grann-noder. De minsta graferna som är reguljära men inte starkt reguljära är de cykliska och över sex noder. Den kompletta grafen Km är starkt reguljär för alla m. En sats av säger att varje k-reguljär graf över 2k + 1 noder har en Hamiltoncykel. * 0-reguljär graf * 1-reguljär graf * 2-reguljär graf * 3-reguljär graf