Handshakes and debts show the difference between two basic kinds of graph
Draw dots for guests at a party and a line whenever two shake hands, and you have an undirected graph, since a handshake always goes both ways. Draw an arrow when one guest owes another money, and the graph becomes directed, because debts need not be mutual. That simple distinction underlies networks everywhere.
In discrete mathematics a graph is a collection of objects, called vertices or nodes, together with a record of which pairs are related, the edges or links. Pictures show vertices as dots and edges as lines or curves between them. The word graph in this sense comes from J. J. Sylvester in 1878, who was inspired by the resemblance between mathematical structures and diagrams of chemical molecules.
Formally, a simple undirected graph is a pair: a set of vertices and a set of unordered vertex pairs. The number of vertices is the graph's order, often written n, and the number of edges its size, written m. The two vertices of an edge are its endpoints, and they are called adjacent; a vertex touching no edge is isolated. The degree of a vertex counts the edges meeting it. In a simple graph of order n, a vertex can have degree at most n minus 1, and the whole graph can hold at most n times n minus 1, divided by two, edges.
Variations relax the rules. A multigraph lets several edges share the same endpoints, and graphs with loops allow an edge from a vertex back to itself, which counts twice toward its degree. A directed graph, or digraph, gives each edge an orientation, running from a tail to a head; the reverse of an edge from x to y is its inverted edge. More general definitions add an incidence function assigning each edge its pair of endpoints, so that multiple arrows between the same vertices become possible.
A graph is fully captured by its adjacency matrix, a square table whose entry in row i and column j records how many edges connect vertex i to vertex j. For a simple graph the entries are just 0 or 1, with zeros down the diagonal. Most work assumes finitely many vertices, since many results about finite graphs fail or need very different proofs in the infinite case.
Source: Graph (discrete mathematics)
