Định lý 5: (công thức Euler) Cho G là một đồ thị phẳng liên thông với $n$ đỉnh, $e$ cạnh. Giả sử $f$ là số mặt của một biểu diễn phẳng của G thì $$n-e+f=2$$ Chứng minh: Giả sử G liên thông. Để chứng minh công thức trên ta sẽ kiểm tra công thức cho các cây và chỉ ra rằng đại lượng $n-e+f$ không đổi khi ta thêm vào 1 cạnh.
Điều này được suy ra từ việc mọi đồ thị liên thông được xây dựng từ cây bằng cách mỗi lần cho thêm vào 1 cạnh, hơn nữa, nếu 1 đồ thị phẳng G nhận được từ đồ thị G' bằng cách thêm vào một cạnh thì G' cũng là đồ thị phẳng.
Ta kiểm tra cho cây, chú ý rằng với 1 cây, $n-e=1$. Hơn nữa, với 1 (biểu diễn phẳng của) cây, chỉ có duy nhất 1 mặt, đó chính là mặt không bị chặn. Thật vậy, mọi mặt bị chặn sẽ làm xuất hiện các chu trình trên đồ thị. Như vậy, với một cây ta có $f=1$ và công thức được kiểm chứng.
Giả sử công thức ta quan tâm đúng cho một đồ thị phẳng G' với $n'$ đỉnh, $e'$ cạnh và $f'$ mặt và sao cho ta có thể thêm 1 cạnh vào G' mà đồ thị mới G vẫn còn phẳng. Thế thì G có $n=n'$ đỉnh, $e=e'+1$ cạnh. Mặt khác cạnh mới thêm vào chia một mặt cũ (của G') thành 2 mặt mới (của G), các mặt khác không đổi. Thật vậy, giả thiết G là phẳng chứng tỏ cạnh mới thêm vào không cắt bất kì cạnh nào khác của G', do đó nằm hoàn toàn trong một trong các mặt của G '. Ngoài ra, tính liên thông của G' chứng tỏ không một đầu mút nào của cạnh thêm vào là cô lập. Như vậy G có $f=f'+1$ mặt. Công thức cho G' kéo theo công thức cho G.
Gõ mệt quá
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]