حال می خواهيم بگوييم گراف چيست. برای تعريف يک گراف مجموعه ای از رئوس به همراه مجموعه ای از يالهارا در نظر می گيريم به طوری که هر دو انتهای هر يال عضوهايي از مجموعه رئوس مفروض باشند. اگر اين گراف را G بناميم، معمولاً مجموعه رئوس آن را با V(G) و مجموعه يالهای آن را با E(G) نمايش می دهند و G برابر با (V(G) , (E(G)) خواهد بود.
يعنی هر گراف دوتايي مرتبی است که مؤلفه اول آن مجموعه رئوس آن گراف و مؤلفه دوم آن مجموعه يالهای آن گراف می باشد به طوری که دو انتهای هر يال عضوهايي از مجموعه رئوس آن هستند. به تعداد رئوس گراف مرتبه و به تعداد يالهای آن اندازه گراف می گوييم.