Lesson 1

Below, we introduce basic notation for graphs. In the following, we assume that \(G(V,E)\) is an undirected graph.

The degree of a node \(v \in V\) is the number of its incident edges: \[\deg(v) = |\{e \in E: v \in e\}|.\] In other words, \(\deg(v)\) is the number of neighbors of \(v\): we say that a node \(u\) is a neighbor of \(v\) if \(u\) and \(v\) are joined by an edge (that is, \(\{u,v\} \in E\)). A node of degree \(0\) is called isolated. The degree of \(G\), denoted \(\Delta(G)\), is the maximum degree of its nodes: \[\Delta(G) = \max \{\deg(v) \colon v \in V\} \ .\]

For example, if \[V=\{A, B, C, K, L, M\} \text{ and }E=\{\{A, C\}, \{B, C\}, \{B, K\}, \{K, A\}, \{K, C\}, \{L, K\}\}\ ,\] then \[\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(K)=4,\ \deg(L)=1,\ \deg(M)=0.\]

from networkx import Graph

graph = Graph(['AC', 'BC', 'BK', 'KA', 'KC', 'LK'])
print(list(graph.degree()))
print(list(graph.neighbors('B')))

[('A', 2), ('B', 2), ('C', 3), ('K', 4), ('L', 1), ('M', 0)]
['C', 'K']