This site is supported by donations to The OEIS Foundation.
Graphs
 “Is the nullgraph a pointless concept?”—Frank Harary, Ronald C. Read.^{[1]}^{[2]}^{[3]}
 “(...) the only good null graph is a dead null graph.”—Brendan McKay.^{[2]}
Graphs are mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context is a pair, i.e. ordered 2tuple, consisting of a collection of "vertices" (or "nodes") and a collection of "edges" that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.
Graphs, with applications in mathematics and computer science, the objects of study in graph theory, is one of the most important branches in discrete mathematics.
Contents
Undirected graphs
Undirected graphs are graphs where there is no distinction between the two vertices associated with each edge, i.e. edges have no orientation.
Example of an undirected graphG = (V, E ) 
V 
E 

V = {1, 2, 3, 4, 5, 6} 
E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 3}, {3, 4}, {4, 5}, {4, 6}}
Directed graphs
Directed graphs (digraphs) are graphs where we distinguish between the two vertices associated with each edge, i.e. edges are oriented.
Example of a directed graphG = (V, E ) 
V 
E 

V = {1, 2, 3, 4, 5, 6} 
E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 3), (3, 4), (4, 3), (4, 5), (4, 6), (5, 1)}
Directed acyclic graphs
Directed acyclic graphs (DAGs) are directed graphs without cycles.
Graph properties
Some graph properties are
 Degree
 Minimum degree
 Average degree
 Maximum degree
 Number of edges
 Number of vertices
Notes
 ↑ F. Harary and R. C. Read, "Is the nullgraph a pointless concept?," pp. 37– 44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. SpringerVerlag, 1974.
 ↑ ^{2.0} ^{2.1} Weisstein, Eric W., Null Graph, from MathWorld—A Wolfram Web Resource.
 ↑ Weisstein, Eric W., Empty Graph, from MathWorld—A Wolfram Web Resource.
External links
 Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, Hadrien Mélot, House of Graphs: a database of interesting graphs, arXiv:1204.3549, 2012.
 G. Brinkmann, J. Goedgebeur, H. Mélot and K. Coolsaet, House of Graphs: a database of interesting graphs, Discrete Applied Mathematics, 161:311314, 2013. Available at http://hog.grinvin.org