📂Graph Theory

Graph Families and Properties

Buildup

Consider a simple graph with a set of $n$ labeled vertices $V = [n] = \left\{ 1 ,\cdots , n \right\}$. The graph can have edges equal to the number of ways to choose two distinct vertices, thus there are exactly $\binom{n}{2}$ such edges. Let’s think about this not just in terms of each edge, but the entire graph. With $n$ vertices fixed, each of the $\binom{n}{2}$ possible edges either exists (1) or does not exist (0), so the set of all graphs with $n$ vertices can be represented as follows: $$2^{\binom{n}{2}}$$ Of course, we are not interested in all of these graphs, so we would like to collect only those that have the properties we need. For example, if there is a set $P$ that consists only of planar graphs with $n$ vertices and a set $O$ that consists only of Eulerian graphs, then these can be defined as subsets of $2^{\binom{n}{2}}$, and it is sufficient to call them properties because if a graph is part of these subsets, it is said to have those properties. For instance, if $G \in \left( P \cap O \right)$, then graph $G$ is both a planar and an Eulerian graph. In other words, graph $G$ has the properties of being planar and Eulerian.

Definition ¹

1. The family of graphs with $n$ labeled vertices is represented using the power set notation as follows: $$2^{\binom{n}{2}}$$
2. A subset $\mathscr{P} \subset 2^{\binom{n}{2}}$ of the graph family $2^{\binom{n}{2}}$ is called a property.
3. The property $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ of being a simple graph with $n$ labeled vertices and $m$ edges is defined as follows: $$\mathscr{G}_{n,m} = \left\{ G \in 2^{\binom{n}{2}} : V(G) = [n] , \left| E(G) \right| = m \right\}$$
4. A property that still holds if one edge $e \notin E(G)$ is added to $G$ is called a monotonically increasing property. In other words, $\mathscr{P}$ satisfying the following is a monotonically increasing property: $$G \in \mathscr{P} \implies (G + e) \in \mathscr{P}$$ Conversely, a property that still holds even if one edge $e \in E(G)$ is removed is called a monotonically decreasing property as follows: $$G \in \mathscr{P} \implies (G - e) \in \mathscr{P}$$ These are collectively referred to as monotone properties.