Într-un graf neorientat, relația dintre două vârfuri între care există o muchie se numește adiacență.