An edge connects two vertices; these two vertices are said to be **incident** to the edge. The **valency** (or **degree**) of a vertex is the number of edges incident to it, with loops being counted twice. In the example graph vertices 1 and 3 have a valency of 2, vertices 2,4 and 5 have a valency of 3 and vertex 6 has a valency of 1. If *E* is finite, then the total valency of the vertices is equal to twice the number of edges. In a digraph, we distinguish the **out degree** (=the number of edges leaving a vertex) and the **in degree** (=the number of edges entering a vertex). The degree of a vertex is equal to the sum of the out degree and the in degree.

Two vertices are considered **adjacent** if an edge exists between them. In the above graph, vertices 1 and 2 are adjacent, but vertices 2 and 4 are not. The set of **neighbors** for a vertex consists of all vertices adjacent to it. In the example graph, vertex 1 has two neighbors: vertex 2 and node 5. For a simple graph, the number of neighbors that a vertex has coincides with its valency.

In computers, a finite directed or undirected graph (with *n* vertices, say) is often represented by its **adjacency matrix**: an *n*-by-*n* matrix whose entry in row *i* and column *j* gives the number of edges from the *i*-th to the *j*-th vertex.

A **path** is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. A path is considered **simple** if none of the vertices in the path are repeated. Two paths are **independent** if they do not have any vertex in common, except the first and last one.

The **length of a path** is the number of edges that the path uses, counting multiple edges multiple times. In the example graph, (1, 2, 5, 1, 2, 3) is a path with length 5, and (5, 2, 1) is a simple path of length 2.

A **weighted graph** associates a value (**weight**) with every edge in the graph. The **weight of a path** in a weighted graph is the sum of the weights of the traversed edges. Sometimes the word **cost** is used instead of **weight**.

If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be **connected**. If it is always possible to establish a path from any vertex to any other vertex even after removing *k*-1 vertices, then the graph is said to be ** k-connected**. Note that a graph is

A **cycle** (or circuit) is a path that begins and ends with the same vertex. Cycles of length 1 are loops. In the example graph, (1, 2, 3, 4, 5, 2, 1) is a cycle of length 6. A **simple cycle** is a cycle which has length at least 3 and in which the beginning vertex only appears once more, as the ending vertex, and the other vertices appear only once. In the above graph (1, 5, 2, 1) is a simple cycle. A graph is called **acyclic** if it contains no simple cycles.

An **articulation point** is a vertex whose removal disconnects a graph. A **bridge** is an edge whose removal disconnects a graph. A **biconnected component** is a maximal set of edges such that any two edges in the set lie on a common simple cycle. The **girth** of a graph is the length of the shortest simple cycle in the graph. The girth of an acyclic graph is defined to be infinity.

A **tree** is a connected acyclic simple graph. Sometimes, one vertex of the tree is distinguished, and called the *root*. Trees are commonly used as data structures in computer science (see tree data structure).

A **forest** is a set of trees; equivalently, a forest is any acyclic graph.

A **subgraph** of the graph *G* is a graph whose vertex set is a subset of the vertex set of *G*, whose edge set is a subset of the edge set of *G*, and such that the map *w* is the restriction of the map from *G*.

A **spanning subgraph** of a graph *G* is a subgraph with the same vertex set as *G*. A **spanning tree** is a spanning subgraph that is a tree. Every graph has a spanning tree.

A **complete graph** is a simple graph in which every vertex is adjacent to every other vertex. The example graph is not complete. The complete graph on *n* vertices is often denoted by *K _{n}*. It has

A regular graph has all vertices of the same valency.

A **universal graph** in a class K of graphs is a simple graph in which every element in K can be embbeded as a subgraph.

A **planar graph** is one which can be drawn in the plane without any two edges intersecting. The example graph is planar; the complete graph on *n* vertices, for *n*> 4, is not planar.

An **Eulerian path** in a graph is a path that uses each edge precisely once. If such a path exists, the graph is called *traversable*. An **Eulerian cycle** is a cycle with uses each edge precisely once.

There is a dual to the Eulerian path/cycle concept. A **Hamiltonian path** in a graph is a path that visits each *vertex* once and only once; and a **Hamiltonian cycle** is a cycle which visits each vertex once and only once.

The example graph does not contain an Eulerian path, but it does contain a Hamiltonian path.

An **empty graph** is the graph whose edge set is empty.

The **null graph** is the graph whose edge set and vertex set are empty.

An **independent set** in a graph is a set of pairwise nonadjacent vertices. In the example above, vertices 1,3, and 6 form an independent set and 3,5, and 6 are another independent set.

A **clique** (pronounced "click") in a graph is a set of pairwise adjacent vertices. In the example graph above, vertices 1, 2 and 5 form a clique.

A **bipartite graph** is any graph whose vertices can be divided into two sets, such that there are no edges between vertices of the same set. A graph can be proved bipartite if there do not exist any circuits of odd length.

A ** k-partite graph** or

A **tournament** is a directed graph in which each pair of vertices is connected by exactly one arc.