Seymour's Second Neighborhood Conjecture

Notations
In graph theory, the most frequently used notations for the set of vertices and the set of edges are V and E, respectively. Furthermore, G(V,E) denotes the graph itself. The square of a graph, whose definition is explained below, is represented by G². On this website, these notations will be maintained.

The author(s) of some of the articles that can be found on this website use(s) different symbols than the ones just mentioned. For example, (the square of) a graph G can also be represented by D (and D²) or Γ (and Γ²). For convenience's sake, the abovementioned notations V, E, G and G² will be used when briefly summarizing or discussing an article, instead of modifying the notations over and over again. Nonetheless, within the context of each separate article all the notations are easily understood.

Definitions
A couple of definitions, which are useful to master before tackling the open problem, are mentioned below. I tried to list the definitions in order of significance, beginning with the most important definition. If you want to read more about a certain subject, please click on the superscript number(s).

simple graph ^{[1] [2]} : An undirected and unweighted graph containing no loops or multiple edges.

directed graph ^[3] : A graph G(V,E) with a set V of vertices and a set E of ordered pairs of vertices, called arcs, directed edges or arrows. If (u,v) ∈ E then we say that u points towards v. The opposite of a directed graph is an undirected graph.

oriented graph ^[4] : A directed graph without symmetric pairs of directed edges.

complete graph ^[5] : A simple graph in which every pair of distinct vertices is connected by a unique edge.

tournament : A complete oriented graph.

square of a graph : The square of a directed graph G = (V,E) is the graph G² = (V,E²) such that (u,w) ∈ E² if and only if (u,v),(v,w) ∈ E.

order of a graph : The order of a graph G = (V,E) is the total number of vertices of G, i.e. |V|.

out-degree of a vertex ^[6] : The number of edges going out of a vertex in a directed graph; also spelled outdegree.

in-degree of a vertex ^[7] : The number of edges coming into a vertex in a directed graph; also spelled indegree.

regular graph ^[8] : A simple graph in which the out-degree of every vertex is equal; also called out-regular graph. In an almost (out-)regular graph, no two out-degrees differ by more than one.

tree ^[9] : A graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree.

leaf : A vertex u ∈ V such that the sum of the out-degree and the in-degree of u is exactly 1.

forest ^[10] : A disjoint union of trees.

oriented cycle : A cycle of edges that are all directed in the same direction; also called directed cycle.

simple graph ^{[1] [2]}	:	An undirected and unweighted graph containing no loops or multiple edges.
directed graph ^[3]	:	A graph G(V,E) with a set V of vertices and a set E of ordered pairs of vertices, called arcs, directed edges or arrows. If (u,v) ∈ E then we say that u points towards v. The opposite of a directed graph is an undirected graph.

oriented graph ^[4]	:	A directed graph without symmetric pairs of directed edges.
complete graph ^[5]	:	A simple graph in which every pair of distinct vertices is connected by a unique edge.
tournament	:	A complete oriented graph.
square of a graph	:	The square of a directed graph G = (V,E) is the graph G² = (V,E²) such that (u,w) ∈ E² if and only if (u,v),(v,w) ∈ E.
order of a graph	:	The order of a graph G = (V,E) is the total number of vertices of G, i.e. \|V\|.
out-degree of a vertex ^[6]	:	The number of edges going out of a vertex in a directed graph; also spelled outdegree.
in-degree of a vertex ^[7]	:	The number of edges coming into a vertex in a directed graph; also spelled indegree.
regular graph ^[8]	:	A simple graph in which the out-degree of every vertex is equal; also called out-regular graph. In an almost (out-)regular graph, no two out-degrees differ by more than one.
tree ^[9]	:	A graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree.

leaf	:	A vertex u ∈ V such that the sum of the out-degree and the in-degree of u is exactly 1.
forest ^[10]	:	A disjoint union of trees.

oriented cycle	:	A cycle of edges that are all directed in the same direction; also called directed cycle.