Adjacent vertex

From Wikipedia, the free encyclopedia

In graph theory, an adjacent vertex of a graph is a vertex that is connected to another vertex with an edge within a graph.

For example, in the image shown is a graph of 6 vertices and 7 edges. Vertex 4 is adjacent to vertices 3, 5, and 6 but it is not adjacent to 1 and 2.

An isolated vertex has no adjacent vertices. The collection of vertices that are adjacent to the same vertex v forms the neighbourhood of v.

[edit] Degree

The degree of a vertex is equal to the number of adjacent vertices.

A special case is a loop that adds two to the degree. This can be understood by letting each connection of the loop edge count as its own adjacent vertex. In other words, a vertex with a loop "sees" itself as an adjacent vertex from both ends of the edge thus adding two, not one, to the degree.

For directed graphs, the degrees are treated differently. (See degree for more details.)

[edit] Adjacency matrix

When all adjacent vertices are tabulated for each vertex in a graph, an adjacency matrix can be formed to show this information.