Terminology Examples

Given the following graph $G(V, E)$:

Sample Graph

Vertices and edges

  • $V=\text{{a,b,c,d,e,f,g,h,i}}$
  • $ \begin{split} E=\lbrace (a,b),(a,d),(b,a),(b,d),(b,h),(c,a),\\(d,h),(d,c),(h,i),(i,h),(e,f),(e,g),(c,i) \rbrace \end{split} $

Neighbors

  • a is $\Gamma(a) = \Gamma(a)^+ + \Gamma(a)^- = 2 + 2 = 4$
  • b is $\Gamma(b) = \Gamma(b)^+ + \Gamma(b)^- = 1 + 3 = 4$
  • c is $\Gamma(c) = \Gamma(c)^+ + \Gamma(c)^- = 2 + 1 = 3$ ...