Graph Theory Concepts

This page provides an overview of several concepts in graph theory. Not all of them are commonly encountered in OI; for OIers, mastering the basic material in this page is sufficient. If you encounter a concept you do not understand while studying, you can return here for reference.

Warning

Definitions in graph theory often differ between textbooks, so their meaning should be determined from the context in which they occur.

Graphs

A graph (graph) is an ordered pair $G=(V(G), E(G))$. Here, $V(G)$ is a nonempty set called the vertex set. Each element of $V$ is called a vertex (vertex) or node (node), or simply a vertex; $E(G)$ is the set of edges between vertices of $V(G)$, called the edge set.

A graph is commonly written as $G=(V,E)$.

When both $V,E$ are finite sets, $G$ is called a finite graph.

When $V$ or $E$ is an infinite set, $G$ is called an infinite graph.

There are several kinds of graphs, including undirected graphs (undirected graph), directed graphs (directed graph), and mixed graphs (mixed graph).

If $G$ is an undirected graph, each element of $E$ is an unordered pair $(u, v)$, called an undirected edge (undirected edge), or simply an edge (edge), where $u, v \in V$. If $e = (u, v)$, then $u$ and $v$ are called the endpoints (endpoint) of $e$.

If $G$ is a directed graph, each element of $E$ is an ordered pair $(u, v)$, sometimes written as $u \to v$, called a directed edge (directed edge) or an arc (arc). When there is no risk of confusion, it may also be called an edge (edge). If $e = u \to v$, then $u$ is called the tail (tail) of $e$, and $v$ is the head (head) of $e$; the tail and head are also called the endpoints (endpoint) of $e$. We also say that $u$ is the immediate predecessor of $v$, and $v$ is the immediate successor of $u$.

Why is the tail the tail and the endpoint the head?

Edges are usually represented by arrows, and an arrow points from its tail to its head.

If $G$ is a mixed graph, $E$ contains both directed edges and undirected edges.

If $G$ has every edge $e_k=(u_k,v_k)$ assigned a number as its weight, then $G$ is called a weighted graph. If all these weights are positive real numbers, $G$ is called a positive-weight graph.

The number of vertices in graph $G$, $\left| V(G) \right|$, is also called the order (order) of graph $G$.

In intuitive terms, a graph consists of several vertices together with edges connecting vertices to one another.

Adjacency

In an undirected graph $G = (V, E)$, if vertex $v$ is an endpoint of edge $e$, then $v$ and $e$ are incident (incident) or adjacent (adjacent). For two vertices $u$ and $v$, if an edge $(u, v)$ exists, then $u$ and $v$ are adjacent (adjacent).

The neighborhood (neighborhood) of a vertex $v \in V$ is the set of all vertices adjacent to it, denoted by $N(v)$.

The neighborhood of a vertex set $S$ is the set of all vertices adjacent to at least one vertex in $S$, denoted by $N(S)$; that is:

$$N(S) = \bigcup_{v \in S} N(v)$$

Simple graphs

Loop (loop): For an edge $e = (u, v)$ in $E$, if $u = v$, then $e$ is called a loop.

Multiple edge (multiple edge): If $E$ contains two identical elements (edges) $e_1, e_2$, they are called a set of multiple edges.

Simple graph (simple graph): A graph with no loops or multiple edges is called a simple graph. Every simple undirected graph with at least two vertices contains two vertices with the same degree. (Pigeonhole principle)

If a graph has a loop or a multiple edge, it is called a multigraph (multigraph).

Warning

In an undirected graph, $(u, v)$ and $(v, u)$ count as a set of multiple edges, whereas in a directed graph, $u \to v$ and $v \to u$ are not multiple edges.

Warning

Unless a problem explicitly says otherwise, loops and multiple edges may exist in a graph, and they must be handled carefully when solving the problem.

Degrees

The number of edges incident to a vertex $v$ is called its degree (degree), denoted by $d(v)$. In particular, for an edge $(v, v)$, each such edge contributes $2$ to $d(v)$.

For a simple undirected graph, $d(v) = \left| N(v) \right|$.

The handshake lemma, also called the fundamental theorem of graph theory, states that for every undirected graph $G = (V, E)$, $\sum_{v \in V} d(v) = 2 \left| E \right|$.

Corollary: In every graph, the number of vertices with odd degree is even.

If $d(v) = 0$, then $v$ is called an isolated vertex (isolated vertex).

If $d(v) = 1$, then $v$ is called a leaf vertex (leaf vertex)/pendant vertex (pendant vertex).

If $2 \mid d(v)$, then $v$ is called an even vertex (even vertex).

If $2 \nmid d(v)$, then $v$ is called an odd vertex (odd vertex). The number of odd vertices in a graph is even.

If $d(v) = \left| V \right| - 1$, then $v$ is called a universal vertex (universal vertex).

For a graph, the minimum degree among all its vertices is called the minimum degree (minimum degree) of $G$ and denoted by $\delta (G)$; the maximum is called the maximum degree (maximum degree) and denoted by $\Delta (G)$. That is, $\delta (G) = \min_{v \in G} d(v)$ and $\Delta (G) = \max_{v \in G} d(v)$.

In a directed graph $G = (V, E)$, the number of edges starting at a vertex $v$ is called its out-degree (out-degree), denoted by $d^+(v)$. The number of edges ending at a vertex $v$ is called its in-degree (in-degree), denoted by $d^-(v)$. Clearly, $d^+(v)+d^-(v)=d(v)$.

For every directed graph $G = (V, E)$, we have:

$$\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right|$$

If every vertex of an undirected graph $G = (V, E)$ has the same fixed degree $k$, then $G$ is called a $k$-regular graph ($k$-regular graph).

If, given a sequence a, there exists a graph G whose degree sequence is a, then a is called graphical.

If, given a sequence a, there exists a simple graph G whose degree sequence is a, then a is called simply graphical.

Paths

Walk (walk): A walk is a sequence of edges joining a sequence of vertices, and may have finite or infinite length. Formally, a finite walk $w$ is a sequence of edges $e_1, e_2, \ldots, e_k$ for which there exists a vertex sequence $v_0, v_1, \ldots, v_k$ satisfying $e_i = (v_{i-1}, v_i)$ for $i \in [1, k]$. Such a walk can be abbreviated as $v_0 \to v_1 \to v_2 \to \cdots \to v_k$. In general, the number of edges $k$ is called the length of the walk (if the edges are weighted, length usually means the sum of the edge weights along the walk, though a problem may define it differently).

Trail (trail): For a walk $w$, if $e_1, e_2, \ldots, e_k$ are pairwise distinct, then $w$ is called a trail.

Path (path) (also called a simple path (simple path)): For a trail $w$, if the vertices in its vertex sequence are pairwise distinct, then $w$ is called a path.

Circuit (circuit): For a trail $w$, if $v_0 = v_k$, then $w$ is called a circuit.

Cycle (cycle) (also called a simple circuit/simple cycle (simple circuit)): For a circuit $w$, if $v_0 = v_k$ is the only pair of vertices repeated in the vertex sequence, then $w$ is called a cycle.

Warning

The definitions of path-related terms may differ from place to place. For example, ‘path’ may refer to the ‘walk’ defined in this article, and ‘cycle’ may refer to the ‘circuit’ defined here. When you encounter similar terminology in a problem without a special qualification such as ‘simple path’/‘non-simple path’ (that is, a ‘walk’ here), it is best to ask exactly which meaning is intended.

Subgraphs

For a graph $G = (V, E)$, if there is another graph $H = (V', E')$ satisfying $V' \subseteq V$ and $E' \subseteq E$, then $H$ is called a subgraph (subgraph) of $G$, written $H \subseteq G$.

For $H \subseteq G$, if for every $\forall u, v \in V'$, whenever $(u, v) \in E$, we also have $(u, v) \in E'$, then $H$ is called an induced subgraph (induced subgraph) of $G$.

It is easy to see that an induced subgraph is determined solely by the vertex set of the subgraph. Therefore, the induced subgraph with vertex set $V'$($V' \subseteq V$) is called the subgraph induced by $V'$, denoted by $G \left[ V' \right]$.

If $H \subseteq G$ and $V' = V$, then $H$ is called a spanning subgraph (spanning subgraph) of $G$.

Clearly, $G$ is its own subgraph, spanning subgraph, and induced subgraph; the edgeless graph is a spanning subgraph of $G$. The original graph $G$ and the edgeless graph are both trivial subgraphs of $G$.

If a spanning subgraph $F$ of an undirected graph $G$ is a $k$-regular graph, then $F$ is called a $k$-factor ($k$-factor) of $G$.

If an induced subgraph $H = G \left[ V^\ast \right]$ of a directed graph $G = (V, E)$ satisfies $\forall v \in V^\ast, (v, u) \in E$, we have $u \in V^\ast$, then $H$ is called a closed subgraph (closed subgraph) of $G$.

Connectivity

Undirected graphs

For an undirected graph $G = (V, E)$ and $u, v \in V$, if there is a walk with $v_0 = u, v_k = v$, then $u$ and $v$ are connected (connected). By definition, every vertex is connected to itself, and the two endpoints of every edge are connected.

If every pair of vertices in an undirected graph $G = (V, E)$ is connected, then $G$ is called a connected graph (connected graph), and this property of $G$ is called connectivity (connectivity).

If $H$ is a connected subgraph of $G$ and there is no $F$ satisfying $H\subsetneq F \subseteq G$ such that $F$ is connected, then $H$ is a connected component (connected component) of $G$ (a maximal connected subgraph).

Directed graphs

For a directed graph $G = (V, E)$ and $u, v \in V$, if there is a walk with $v_0 = u, v_k = v$, then $u$ can reach $v$. By definition, every vertex can reach itself, and the tail of every edge can reach its head. (Connectivity in an undirected graph can also be viewed as mutual reachability.)

If every pair of vertices in a directed graph can reach each other, then the graph is strongly connected (strongly connected).

If replacing every edge of a directed graph by an undirected edge produces a connected graph, then the original directed graph is weakly connected (weakly connected).

As with connected components, there are weakly connected components (weakly connected component) (maximal weakly connected subgraphs) and strongly connected components (strongly connected component) (maximal strongly connected subgraphs).

For related algorithms, see strongly connected components.

Cuts

For related algorithms, see cut vertices and bridges and biconnected components.

In this section, ‘connected’ for directed graphs generally means ‘strongly connected’.

For a connected graph $G = (V, E)$, if $V'\subseteq V$ and $G\left[V\setminus V'\right]$ (that is, the graph obtained by deleting the vertices in $V'$ from $G$) is not connected, then $V'$ is a vertex cut (vertex cut/separating set) of $G$. A vertex cut of size one is also called a cut vertex (cut vertex).

For a connected graph $G = (V, E)$ and an integer $k$, if $|V|\ge k+1$ and $G$ has no vertex cut of size $k-1$, then $G$ is $k$-vertex-connected ($k$-vertex-connected). The largest $k$ for which this holds is called the vertex connectivity (vertex connectivity) of $G$, denoted by $\kappa(G)$. (For a non-complete graph, vertex connectivity is the size of the smallest vertex cut, while the vertex connectivity of the complete graph $K_n$ is $n-1$.)

For a graph $G = (V, E)$ and $u, v\in V$ satisfying $u\ne v$, with $u$ and $v$ nonadjacent and $u$ able to reach $v$, if $V'\subseteq V$, $u, v\notin V'$, and $u$ and $v$ are disconnected in $G\left[V\setminus V'\right]$, then $V'$ is called a vertex cut from $u$ to $v$. The size of the smallest vertex cut from $u$ to $v$ is called the local connectivity (local connectivity) between $u$ and $v$, denoted by $\kappa(u, v)$.

A similar definition can be made for edges:

For a connected graph $G = (V, E)$, if $E'\subseteq E$ and $G' = (V, E\setminus E')$ (that is, the graph obtained by deleting the edges in $E'$ from $G$) is not connected, then $E'$ is an edge cut (edge cut) of $G$. An edge cut of size one is also called a bridge (bridge).

For a connected graph $G = (V, E)$ and an integer $k$, if $G$ has no edge cut of size $k-1$, then $G$ is $k$-edge-connected ($k$-edge-connected). The largest $k$ for which this holds is called the edge connectivity (edge connectivity) of $G$, denoted by $\lambda(G)$. (For any graph, edge connectivity is the size of the smallest edge cut.)

For a graph $G = (V, E)$ and $u, v\in V$ satisfying $u\ne v$, with $u$ able to reach $v$, if $E'\subseteq E$ and $u$ and $v$ are disconnected in $G'=(V, E\setminus E')$, then $E'$ is called an edge cut from $u$ to $v$. The size of the smallest edge cut from $u$ to $v$ is called the local edge-connectivity (local edge-connectivity) between $u$ and $v$, denoted by $\lambda(u, v)$.

Biconnected (biconnected) is almost exactly the same as $2$-vertex-connected, except that a graph consisting of two vertices joined by one edge is biconnected but is not $2$-vertex-connected. In other words, a connected graph with no cut vertex is biconnected.

Edge-biconnected ($2$-edge-connected) is exactly the same as $2$-edge-connected. In other words, a connected graph with no bridge is edge-biconnected.

As with connected components, there are biconnected components (biconnected component) (maximal biconnected subgraphs) and Edge-biconnected components ($2$-edge-connected component) (maximal edge-biconnected subgraphs).

Whitney's theorem: For any graph $G$, $\kappa(G)\le \lambda(G)\le \delta(G)$. (The three quantities in the inequality are vertex connectivity, edge connectivity, and minimum degree, respectively.)

Sparse and dense graphs

If a graph has far fewer edges than the square of its number of vertices, it is a sparse graph (sparse graph).

If a graph has a number of edges close to the square of its number of vertices, it is a dense graph (dense graph).

These two concepts have no strict definitions. They are generally used to discuss the efficiency difference between algorithms with time complexity $O(|V|^2)$ and algorithms with $O(|E|)$ complexity (the two algorithms have comparable efficiency on dense graphs, whereas the $O(|E|)$ algorithm is significantly more efficient on sparse graphs).

Complement graphs

For an undirected simple graph $G = (V, E)$, its complement graph (complement graph) is the graph, denoted by $\bar G$, satisfying $V \left( \bar G \right) = V \left( G \right)$ and, for every pair of vertices $(u, v)$, $(u, v) \in E \left( \bar G \right)$ if and only if $(u, v) \notin E \left( G \right)$.

Transpose graphs

For a directed graph $G = (V, E)$, its transpose graph (transpose graph) is the graph with the same vertex set and every edge reversed. In other words, if the transpose of $G$ is $G'=(V, E')$, then $E'=\{(v, u)|(u, v)\in E\}$.

Special graphs

If an undirected simple graph $G$ has an edge between every pair of distinct vertices, then $G$ is a complete graph (complete graph); the complete graph of order $n$ is denoted by $K_n$. If a directed graph $G$ has two oppositely directed edges between every pair of distinct vertices, then $G$ is a complete digraph (complete digraph).

A graph with an empty edge set is called an edgeless graph (edgeless graph), an empty graph (empty graph), or a null graph (null graph). An edgeless graph of order $n$ is denoted by $\overline{K}_n$ or $N_n$. $N_n$ and $K_n$ are complements of each other.

Warning

Null graph (null graph) may also refer to an order-zero graph (order-zero graph) $K_0$, whose vertex and edge sets are both empty.

If a simple directed graph $G$ has exactly one directed edge between every pair of distinct vertices, then $G$ is called a tournament graph (tournament graph).

If all edges of an undirected simple graph $G = \left( V, E \right)$ form exactly one cycle, then $G$ is called a cycle graph (cycle graph). A cycle graph of order $n$($n \geq 3$) is denoted by $C_n$. It is easy to see that a graph is a cycle graph if and only if it is a connected $2$-regular graph.

If an undirected simple graph $G = \left( V, E \right)$ has a vertex $v$ that is universal and no edges between any of the other vertices, then $G$ is called a star graph (star graph). A star graph of order $n + 1$($n \geq 1$) is denoted by $S_n$.

If an undirected simple graph $G = \left( V, E \right)$ has a vertex $v$ that is universal and the other vertices form a cycle, then $G$ is called a wheel graph (wheel graph). A wheel graph of order $n + 1$($n \geq 3$) is denoted by $W_n$.

If all edges of an undirected simple graph $G = \left( V, E \right)$ form exactly one simple path, then $G$ is called a chain/path graph (chain/path graph). A chain of order $n$ is denoted by $P_n$. It is easy to see that a chain is obtained by deleting one edge from a cycle graph.

If an undirected connected graph contains no cycle, then it is a tree (tree). For related content, see Basic tree algorithms.

If an undirected connected graph contains exactly one cycle, then it is a pseudotree (pseudotree).

If every vertex of a directed weakly connected graph has in-degree $1$, then it is an outward-oriented pseudotree.

If every vertex of a directed weakly connected graph has out-degree $1$, then it is an inward-oriented pseudotree.

Several trees can form a forest (forest); several pseudotrees can form a pseudoforest (pseudoforest); several outward-oriented pseudotrees can form a forest of outward-oriented pseudotrees; and several inward-oriented pseudotrees can form a forest of inward-oriented pseudotrees (functional graph).

If every edge of an undirected connected graph belongs to at most one cycle, then it is a cactus (cactus). Several cacti can form a desert.

If the vertex set of a graph can be divided into two parts with no edges within either part, then the graph is a bipartite graph (bipartite graph). If every pair of vertices in different parts of a bipartite graph is connected by an edge, then it is a complete bipartite graph (complete bipartite graph/biclique). A complete bipartite graph whose two parts contain $n$ and $m$ vertices is denoted by $K_{n, m}$. For related content, see Bipartite graphs.

If a graph can be drawn on a plane with no two edges intersecting away from their endpoints, then it is a planar graph (planar graph). For a simple connected planar graph $G=(V, E)$ with $V\ge 3$, $|E|\le 3|V|-6$.
Kuratowski's theorem: A graph is planar if and only if it has no subgraph homeomorphic to $K_5$ or $K_{3, 3}$. Graphs $G$ and $G'$ are homeomorphic if both can be transformed into the same graph by adding several degree-$2$ vertices¹ on edges.

Isomorphism

For two graphs $G$ and $H$, if there is a bijection $f : V(G) \to V(H)$ satisfying $(u,v)\in E(G)$ if and only if $(f(u),f(v))\in E(H)$, then $f$ is an isomorphism (isomorphism) from $G$ to $H$, and graphs $G$ and $H$ are isomorphic (isomorphic), written $G \cong H$.

It follows from the definition that if $G \cong H$, then all of the following must hold:

• $|V(G)|=|V(H)|,|E(G)|=|E(H)|$
• $G$ and $H$ have the same nonincreasing sequence of vertex degrees
• $G$ and $H$ have isomorphic induced subgraphs

Binary operations on undirected simple graphs

For undirected simple graphs, we can define the following binary operations:

Intersection (intersection): For graphs $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$, their intersection is defined as $G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)$.

It is easy to prove that the intersection of two undirected simple graphs is still an undirected simple graph.

Union (union): For graphs $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$, their union is defined as $G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)$.

Sum (sum)/direct sum (direct sum): For $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$, construct any $H' \cong H$ such that $V \left( H' \right) \cap V_1 = \varnothing$($H'$ may be equal to $H$). Then any graph isomorphic to $G \cup H'$ is called the sum/direct sum/disjoint union of $G$ and $H$, denoted by $G + H$ or $G \oplus H$.

If the vertex sets of $G$ and $H$ are already disjoint, then $G \cup H = G + H$.

For example, a forest can be defined as the sum of several trees.

Difference between union and sum

The ‘union’ can be understood as merging vertices and edges with the same names in the two graphs, whereas the ‘sum’ does not.

Special vertex and edge sets

Dominating sets

For an undirected graph $G=(V, E)$, if $V'\subseteq V$ and $\forall v\in(V\setminus V')$ there is an edge $(u, v)\in E$ with $u\in V'$, then $V'$ is a dominating set (dominating set) of $G$.

The size of a smallest dominating set of an undirected graph $G$ is denoted by $\gamma(G)$. Finding a minimum dominating set of a graph is NP-hard.

For a directed graph $G=(V, E)$, if $V'\subseteq V$ and $\forall v\in(V\setminus V')$ there is an edge $(u, v)\in E$ with $u\in V'$, then $V'$ is an out-dominating set (out-dominating set) of $G$. Similarly, an in-dominating set (in-dominating set) can be defined for directed graphs.

The minimum size of an out-dominating set of a directed graph $G$ is denoted by $\gamma^+(G)$, and the minimum size of an in-dominating set is denoted by $\gamma^-(G)$.

Edge-dominating sets

For a graph $G=(V, E)$, if $E'\subseteq E$ and $\forall e\in(E\setminus E')$ there is an edge in $E'$ sharing an endpoint with it, then $E'$ is an edge-dominating set (edge dominating set) of $G$.

Finding a minimum edge-dominating set of a graph is NP-hard.

Independent sets

For a graph $G=(V, E)$, if $V'\subseteq V$ and no two vertices in $V'$ are adjacent, then $V'$ is an independent set (independent set) of $G$.

The size of a largest independent set of graph $G$ is denoted by $\alpha(G)$. Finding a maximum independent set of a graph is NP-hard.

Matchings

For a graph $G=(V, E)$, if $E'\subseteq E$, every two distinct edges in $E'$ have no common endpoint, and no edge in $E'$ is a loop, then $E'$ is a matching (matching) of $G$, also called an independent edge set (independent edge set). If a vertex is an endpoint of an edge in the matching, it is called matched (matched)/saturated (saturated); otherwise, it is called unmatched (unmatched).

A matching with the largest number of edges is called a maximum-cardinality matching (maximum-cardinality matching) of a graph. The size of a maximum matching in graph $G$ is denoted by $\nu(G)$.

If the edges are weighted, a matching with the largest total weight is called a maximum-weight matching (maximum-weight matching) of a graph.

If adding any edge to a matching makes it no longer a matching, then the matching is a maximal matching (maximal matching). A largest maximal matching is a maximum matching, and every maximum matching is maximal. Every maximal matching is an edge-dominating set, but an edge-dominating set need not be a matching. A minimum maximal matching and a minimum edge-dominating set have the same size, but a minimum edge-dominating set need not be a matching. Finding a minimum maximal matching is NP-hard.

If every vertex is matched in a matching, then the matching is a perfect matching (perfect matching). If exactly one vertex is unmatched in a matching, then the matching is a near-perfect matching (near-perfect matching).

Counting the matchings or perfect matchings of an ordinary graph or a bipartite graph is #P-complete.

For a matching $M$, if a path starts at an unmatched vertex and each pair of consecutive edges consists of one edge in the matching and one edge outside the matching, then the path is called an alternating path (alternating path); an alternating path that ends at an unmatched vertex is called an augmenting path (augmenting path).

Tutte's theorem: An undirected graph $G$ of order $n$ has a perfect matching if and only if, for every $V' \subset V(G)$, $p_{\text{odd}}(G-V')\leq |V'|$, where $p_{\text{odd}}$ denotes the number of connected components of odd order.

Tutte's theorem (corollary): Every bridgeless 3-regular graph has a perfect matching.

Vertex covers

For a graph $G=(V, E)$, if $V'\subseteq V$ and $\forall e\in E$ at least one endpoint of $e$ belongs to $V'$, then $V'$ is a vertex cover (vertex cover) of $G$.

Every vertex cover is a dominating set, but a minimal vertex cover need not be a minimal dominating set.

A vertex set is a vertex cover if and only if its complement is an independent set; therefore, the complement of a minimum vertex cover is a maximum independent set. Finding a minimum vertex cover of a graph is NP-hard.

The size of any matching in a graph is no greater than the size of any vertex cover of that graph. In the complete bipartite graph $K_{n, m}$, both the maximum matching size and the minimum vertex cover size are $\min(n, m)$.

Edge covers

For a graph $G=(V, E)$, if $E'\subseteq E$ and $\forall v\in V$, $v$ is adjacent to at least one edge in $E'$, then $E'$ is an edge cover (edge cover) of $G$.

The size of a minimum edge cover is denoted by $\rho(G)$. It can be obtained by greedily extending a maximum matching: for every unmatched vertex, add one incident edge to the maximum matching; the result is a minimum edge cover.

A maximum matching can also be obtained from a minimum edge cover: for every pair of edges in the minimum edge cover that share a vertex, delete one of them.

For a graph, the size of a minimum edge cover plus the size of a maximum matching equals the number of vertices, namely $\rho(G)+\nu(G)=|V(G)|$.

For a graph, the size of a maximum matching is no greater than the size of a minimum edge cover, namely $\nu(G)\le\rho(G)$. In particular, a perfect matching is always a minimum edge cover, and it is the only case in which equality holds in the formula above.

The size of any independent set in a graph is no greater than the size of any edge cover of that graph. In the complete bipartite graph $K_{n, m}$, both the maximum independent set size and the minimum edge cover size are $\max(n, m)$.

Cliques

For a graph $G=(V, E)$, if $V'\subseteq V$ and every two distinct vertices in $V'$ are adjacent, then $V'$ is a clique (clique) of $G$. The subgraph induced by a clique is a complete graph.

If adding any vertex to a clique makes it no longer a clique, then the clique is a maximal clique (maximal clique).

The size of a maximum clique in a graph is denoted by $\omega(G)$. It equals the size of a maximum independent set in its complement, namely $\omega(G)=\alpha(\bar{G})$. Finding a maximum clique in a graph is NP-hard.

References

OI Graph Transit Station - A review of graph theory concepts

Wikipedia (and the corresponding entries for related concepts)

Discrete Mathematics (Revised Edition), compiled by Tian Wencheng and Zhou Luxin, Tianjin Literature Press, pp. 184–187

Dai Yiqi, Hu Guanzhang, and Chen Wei. Graph Theory and Algebraic Structures [M]. Beijing: Tsinghua University Press, 1995.

Footnotes

1. This operation is also called a subdivision (subdivision). ↩