Разница между смежностью и инцидентностью в теории графов заключается в том, что смежность относится к объектам одного вида, а инцидентность — к объектам другого вида. 24

Смежность применяется к вершинам и рёбрам. 2

• Смежность вершин — это отношение между двумя вершинами, в котором существует ребро, их соединяющее. 5
• Смежность рёбер — это отношение между двумя рёбрами, в котором существует вершина, их соединяющая. 5

Инцидентность применяется к рёбрам и вершинам. 2

• Инцидентность вершин — это когда вершина является началом или концом ребра. 5
• Инцидентность рёбер — это когда ребро выходит из вершины. 2

Таким образом, смежность — это отношение между однородными элементами графа, а инцидентность — между разнородными. 4