A graph $$ G$$ is an ordered pair $$ V,E$$ of sets $$ V$$ of vertices and $$ E$$ of edges, that are disjoint together with an incedence function $$ \mathrm{\varphi <!--\; \varphi \; -->}:E\to <!--\; \to \; -->V\times <!--\; \times \; -->V$$ that associates with

Suppose that $$ G=(V,E)$$ is a graph, then we say that the degree of a vertex $$ v$$ is the number of other vertices connected to it with an edge. We define the syntax $$ \mathrm{deg}:V\to <!--\; \to \; -->{\mathbb{N}}^0$$ to be the function that maps a node to it's degree.

Suppose that we have a graph $$ G$$, then we say that $$ G$$ has branching factor $$ b\in <!--\; \in \; -->{\mathbb{N}}_1$$, if every vertex has degree $$ b$$

Suppose that $$ G$$ is a finite graph, then the average branching factor of the graph is defined as $\[ \frac{\underset{v\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}\mathrm{deg}<!--\; \; -->\left(v\right)}{|<!--\; |\; -->V|<!--\; |\; -->}\in <!--\; \in \; -->\mathbb{Q} \]$

Suppose that we have a graph $$ G$$, then we say that $$ G$$ has a maximum branching factor of $$ b\in <!--\; \in \; -->{\mathbb{N}}_0$$, if every vertex has degree at most $$ b$$

A tuple $$ (v_1,v_2,\dots <!--\; \dots \; -->v_n)\in <!--\; \in \; -->V^n$$ is said to be a path if for every $$ i\in <!--\; \in \; -->[1\dots <!--\; \dots \; -->n-<!--\; -\; -->1]$$, $$ \{v_i,v_{i+1}\}\in <!--\; \in \; -->E$$.

Suppose that $$ u,v\in <!--\; \in \; -->V$$, then we say that $$ u,v$$ are connected if there is a path $$ v_1,v_2,\dots <!--\; \dots \; -->,v_n$$ where $$ v_1=u$$ and $$ v_n=v$$

Given a graph $$ G$$ we say that it is connected when for every $$ u,v\in <!--\; \in \; -->V$$, we have that $$ u$$ and $$ v$$ are connected.