What is the maximum number of edges in a simple directed graph with V vertices?
Each vertex can have directed edges to V - 1 other vertices. Total directed edges = V * (V - 1).
In an undirected graph, if the degree of every vertex is at least 2, the graph MUST contain at least one:
If every vertex in a finite graph has degree >= 2, following any path eventually visits an already-visited vertex, forming a cycle.
In a graph $G = (V$, E), the sum of in-degrees of all vertices is equal to:
Each directed edge contributes exactly 1 to the in-degree of its head vertex. Thus sum of in-degrees = |E|.
In a graph $G = (V$, E), the sum of out-degrees of all vertices is equal to:
Each directed edge contributes exactly 1 to the out-degree of its tail vertex. Thus sum of out-degrees = |E|.
How many distinct spanning trees can be formed from a complete graph $K_{n}$ with n labeled vertices (Cayley's Formula)?
Cayley's Formula proves that the number of labeled spanning trees in $K_{n}$ is $n^{n-2}$.