Понятия смежности и инцидентности в теории графов связаны следующим образом:

1. Смежность применяется к объектам одного вида — смежными между собой могут быть вершины и рёбра. 2 Одна вершина смежна другой, если они соединены дугой или ребром. 2 Одно ребро смежно другому ребру, если у них есть общая вершина, из которой они выходят. 2
2. Инцидентность применяется к рёбрам и вершинам. 2 Ребро инцидентно вершине, если это ребро выходит из вершины. 2 Две вершины называются инцидентными, если у них есть общее ребро. 3

Таким образом, смежность описывает отношения между объектами одного вида, а инцидентность — между рёбрами и вершинами: одно ребро смежно другому ребру, если у них есть общая вершина, из которой они выходят, а ребро инцидентно вершине, если это ребро выходит из неё. 2