A graph is represented as G = ( V, E ), where
A graph with p vertices and q edges is called a p, q-graph.
If an edge e = (a, b) is an edge in a graph, then
The degree of a vertex v
is the number of vertices adjacent to v.
(This equals the number of edges incident with v).
An isolated vertex is a vertex of degree 0.
A graph is regular if the degrees of all vertices are equal.
A graph is r-regular if
, .
Two graphs G = (V, E) and H = (U, F) are called isomorphic if there is a one-to-one correspondence between V and U which preserves all adjacencies.
Odd-Degrees CorollaryEvery graph contains an even number of vertices of odd degree. |
A walk is called a path if it does not repeat any vertex.
A graph is called connected if, for any two vertices u and v of the graph, there is a walk from u to v.
A connected component is a maximal connected subgraph. A subset S of vertices of a graph G is a connected component if and only if:
A closed walk is a walk whose first and last vertices are the same.
A cycle is a closed walk which does not repeat any vertex, except for the first and the last.
A set of vertices is called a clique if every pair of vertices in the set is adjacent.
An independent set (resp. a clique) is called maximal if no other independent set (resp. clique) contains it.
An independent set (resp. a clique) is called maximum if its cardinality is maximal among all independent sets (resp. clique) in the graph.
(resp. ) denotes the maximum size of an independent set (resp. a clique) in a graph G.
A set of edges in a graph is called a matching if no two of them are incident to the same vertex. denotes the maximum size of a matching in a graph G.
A graph is called k-colorable if it has a k-coloring.
The chromatic number of a graph G is the minimal k for which the graph is k-colorable.
A graph with chromatic number k is called k-chromatic.