Adjacency

• An edge meets or is incident to the vertices i and j in V. If such an edge exists, the two vertices are adjacent. For example, vertices and are adjacent in the graph in figure 1, but vertices and are not adjacent.
• A graph can be represented by a vertex-edge incidence matrix A with entries given by

  

  For example, the graph in figure 1

   
  Figure 1: A graph  
  

  has incidence matrix

  

  where the edges are listed in the order (1,2), (1,3), (1,4), (2,3), (2,5), (3,6), (4,5), (4,6), and (5,6). Notice that every column of the incidence matrix contains exactly two ``ones''.

• The number of edges incident to a node is called the degree of the node. This is equal to the number of ``ones'' in the corresponding row of the incidence matrix. Every node in the graph in figure 1 has degree 3.
• A graph with m vertices is called complete if it contains all possible edges, so the degree of every vertex is then m-1. This graph is written  .