Knowlpedia

Graph: vertices and edges

Defines vertices and edges in a graph, along with incidence and adjacency.

A (simple, undirected) graph is an G=(V,E)G=(V,E) where:

  • VV is a of vertices (or nodes).
  • EE is a set of edges, where each edge is a 2-element subset {u,v}⊆V\{u,v\}\subseteq V.

If {u,v}∈E\{u,v\}\in E, then:

  • uu and vv are the endpoints of the edge,
  • uu and vv are adjacent (neighbors), and
  • the edge is incident to each of its endpoints.
Remarks

Common notation. In a simple undirected graph, the edge {u,v}\{u,v\} is often written as uvuv.

The of a vertex counts its neighbors.

Variants. Depending on context, one may also allow:

  • Directed edges (u,v)(u,v) (a directed graph),
  • loops {u,u}\{u,u\}, and/or
  • multiple edges between the same pair of vertices (a multigraph).

Unless stated otherwise, “graph” typically means simple, undirected.

A graph is called if it has finitely many vertices (and hence finitely many edges in the simple case).