> [!NOTE] Definition (Vertex) > Given a [[Graphs|graph]] $G:=(V,E)$, the elements of the [[Sets|set]] $V$ are its *vertices* (or *nodes*, or *points*). # Properties > [!NOTE] Definition (Incidence with edge) > A vertex $v$ is *incident* with an edge $e\in E$ if $v\in e.$ > [!NOTE] Definition (Adjacent Nodes in Undirected Graph) > Two nodes $u,v$ of an undirected graph are **adjacent** iff $\{ u,v \} \in E$ (i.e. they are incident with a common edge). > > [!NOTE] Definition (Neighbourhood) > If $G$ is undirected > - we say $v\in V$ is a **neighbour** of $u\in V$ if $\{ u,v \}\in E.$ > - The open neighbourhood of $v$ is defined by $N_{G}(v)=\{ u \in V \mid \{ u,v \} \in E \}.$ >- The closed neighbourhood of $v$ is given by $N_{G}[v]=\{ v \} \cup N_{G}(v).$ > >If $G$ is directed >- The out-neighbourhood of $v\in G$ is given by $\{ u \in V \mid (v,u ) \in E\}.$ >- The in-neighbourhood of $v\in G$ is given by $\{ u\in V \mid (u,v) \in E \}$ > [!Definition] Definition (Degree) > The degree of a vertex in an undirected graph is the number of edges that at $v.$ > > If the graph is simple, then the degree of $v$ is the cardinality of its open neighbourhood. > > We can define in-degree and out-degree similarly for nodes of directed graphs. > > Equivalently, given its [[Adjacency Matrix|adjacency matrix]] $\deg(i)= \sum_{j=1}^{N} A_{ij}$ > [!Lemma] Lemma (Handshaking lemma) > In any graph $G=(V,E)$, $\sum_{v\in V} \deg (v) = 2 \cdot |E|$ ^b65bed >See [[Degree-Sum Formula|Proof]].