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

Tồn tại một cạnh của G là cạnh vô hướng

Mọi cạnh của G là cạnh vô hướng

Có hai cạnh của G là cạnh vô hướng

Mọi cạnh của G là cạnh có hướng