Fundamentals of combinatorics

If any two types of structures can be considered to be the fundamentals of combinatorics it is graphs and orders. Other structures are constructed after these simpler ones, but these are two of the simplest and most fundamental structures. Orders such as lattices and graphs are widely used throughout combinatorics, which is why they are so fundamental.

It is worthwhile to consider the metric properties of graphs. Graphs aren't just another structure, they are a way of defining the distance relations between points. There are metric properties of graphs like eccentricity, center, radius, diameter, and so on. It is worth considering this, because metrics and orders are perhaps the most fundamental concepts in general. With all this about the central importance of graphs and orders said, it is worth considering that they are not completely separate subjects from one another. Orders and graphs can be formed from one another in the manner listed below.

Orders derived from graphs:
The most immediate order that can be derived from a graph is adjacency containment. This forms a preorder, in which two elements are related if the set of nodes they are adjacent are included in one another. For the class of trivially perfect graphs, this preorder fully determines the graph. For example, a cluster graph is equivalent to a symmetric preorder. Cotrivially perfect graphs are determined by their coadjacency containment. Otherwise, the preorder only provides partial information on the graph.

Graphs derived from orders:
The most immediate graph that can be formed from an order is the comparability graph. The complement of this is the cocomparability graph. Both the comparability graph and the cocomparability graph are instances of perfect graphs. The comparability graph is the most general graph that can be formed from a partial order, but it doesn't always suffice. Another graph that can be formed by a partial order, particularly a hereditary discrete partial order, is the covering graph determined by the comparability of the transitive reduction of the partial order. This is a subgraph of the comparability graph.