Definitions for Graphs

• A graph consists of a set of vertices, together with the information which pairs of vertices are adjacent. Adjaceny is symmetric, meaning that if vertex x is adjacent to vertex y, then vertex y is also adjacent to vertex x. If two vertices are adjacent, then we call the pair an edge of the graph.
• Two adjacent vertices are called neighbors of each other.
• The degree d_G(x) of a vertex x in a graph G is the number of its neighbors.
• A walk is a sequence x, y, z, ... w of vertices where any two consecutive vertices are adjacent. Its length is the number of edges travelled, one less than the number of vertices of the walk.
• A path is a wlk with no vertex repeated.
• The distance d(x,y) between two vertices in a graph is the smallest length of a path (or walk).
• A graph is connected if there is some path between every pair of vertices.
• The average distance of a connected graph is the average of the distances occuring between pairs of verices.
• The diameter diam(G) of a connected graph G is the maximum occuring distance between vertices.