## Graphs, An Introduction

### Introduction

A graph is a set of vertices V,
and a set of edges E that connect pairs of points in V.
Edges are actually determined by a symmetric irreflexive relation on V cross V.
Some graphs may include loops (a point connected to itself) or multiple edges
(many lines connecting a pair of points), but they are the exceptions.
Unless otherwise indicated, the term "graph" refers to the definition above.
A digraph contains vertices and edges as above,
but the edges are directed.
In other words, the edge relation need not be symmetric.
The edge v1→v2 does not imply the edge v2→v1.
Edges are drawn using arrows, rather than line segments.
Again, loops and multiple edges are usually prohibited.

A vertex has degree n if there are n edges connecting that vertex to other vertices.
The number of edges is half the sum of the degrees.

In a digraph, vertices have indegrees and outdegrees.
The number of directed edges is the sum of the indegrees, or the sum of the outdegrees.