Đồ thị G = (V,E) được gọi là đồ thị vô hướng nếu:

Ma trận kề gồm các phần tử đối xứng nhau qua đường chéo chính

Ma trận kề gồm các phần tử không đối xứng nhau qua đường chéo chính

Các phần tử trên đướng chéo chính bằng 1

Các phần tử trên đường chéo phụ bằng 1

Các cạnh e₁,e₂,…,e_n kề nhau

Các đỉnh v₀ = s, v₁, v₂, …,v_n = t kề nhau, các cạnh e_i=(v_i-1,vi) đôi một khác nhau, i = 0..n

Các cạnh e₁,e₂,…,e_n không kề nhau

Các đỉnh v₀ = s, v₁, v₂, …,v_n = t không kề nhau

Bậc của các đỉnh trong đồ thị -2

Bậc của các đỉnh trong đồ thị -n

Bậc của các đỉnh trong đồ thị -n/2

Bậc của các đỉnh trong đồ thị -n/4

Có thể vẽ được trên một mặt phẳng mà có các cạnh cắt nhau ở đỉnh ngoài

Có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau

Có thể vẽ được trên một mặt phẳng mà có hai cạnh bất kỳ cắt nhau

Có thể vẽ được trên một mặt phẳng mà không có quá hai cạnh cắt nhau

C, A, B, E, F, D, G, H, K, C, N

C, A, B, K, N, I, D, E, F, H, G

C, A, E, G, B, D, F, H, K, I, N

C, A, E, G, F, H, N, B, D, I, K

2n

2ⁿ

2ⁿ+1

2ⁿ-1

2

3

4

5

{(1,a), (3,3), (2,a)}

{(2,2), (2,c), (3,b)}

{(1,a), (2,2), (3,1)}

{(2,c), (2,2), (b,3)}

6

7

8

9

16

14

2

32