Công thức Euler cho đồ thị phẳng

Cơ sở quy nạp. Nếu $E$ $= 0$ và đồ thị liên thông, nó phải chỉ gồm một đỉnh duy nhất ($V=1$), và có đúng một mặt, toàn bộ mặt phẳng không bị chặn ($F=1$). Khi đó $1 - 0 + 1 = 2$ đúng.

Bước quy nạp, trường hợp 1: một cạnh nằm trên chu trình. Giả sử công thức đúng với mọi đồ thị phẳng liên thông đã vẽ có ít hơn $E$ cạnh, và cho đồ thị có $E$ $\ge 1$ cạnh. Nếu một cạnh $e$ nằm trên chu trình, thì bỏ $e$ vẫn giữ đồ thị liên thông (phần còn lại của chu trình vẫn nối hai đầu mút của nó). Bỏ $e$ nhập hai mặt ở hai phía của nó thành một mặt duy nhất, nên đồ thị nhỏ hơn có $V$ đỉnh, $E - 1$ cạnh và $F - 1$ mặt. Theo giả thiết quy nạp, $V - (E-1) + (F-1) = 2$, rút gọn thành $V - E + F = 2$.

Bước quy nạp, trường hợp 2: không cạnh nào nằm trên chu trình. Khi đó mọi cạnh đều là cầu, nghĩa là đồ thị hoàn toàn không có chu trình, tức nó là một cây. Một cây vẽ trên mặt phẳng có đúng một mặt ($F = 1$, miền không bị chặn duy nhất, vì không có chu trình nào để bao một miền bị chặn), và một sự kiện chuẩn về cây là cây có $V$ đỉnh thì có đúng $E = V - 1$ cạnh. Thay vào, $V - E + F = V - (V - 1) + 1 = 2$.

Kết luận. Mọi trường hợp đều quy về công thức đúng, hoặc quy về (qua việc bỏ một cạnh) một đồ thị nhỏ hơn nơi nó đúng theo quy nạp, nên $V - E + F = 2$ với mọi đồ thị phẳng liên thông đã vẽ.