Seymour's Second Neighborhood Conjecture

Notations & definitions
The open problem
Incorrect proofs
Special cases
Correct(?) proofs
Related problems
Other results
About this website


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 G2. 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 D2) or Γ (and Γ2). For convenience's sake, the abovementioned notations V, E, G and G2 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.


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.
    Example of a directed 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 G2 = (V,E2) such that (u,w) ∈ E2 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.
    Example of a tree
  • leaf :A vertex uV such that the sum of the out-degree and the in-degree of u is exactly 1.
  • forest [10]:A disjoint union of trees.
    Example of a forest
  • oriented cycle :A cycle of edges that are all directed in the same direction; also called directed cycle.
    Example of an oriented cycle

    Back to top