Graph theory is really a collection of closely related theories which differ in some details, depending on a few basic choices:
Are our graphs directed or undirected?
How many vertices and edges do we allow? Finitely many? Countably many, uncountably many?
Are self-loops, i.e. edges connecting a vertex to itself, allowed?
Can there be more than one edge between a pair of vertices?
For different applications different combinations of these are useful. We don’t have time to cover all of them though and so will have to make some choices.
I’ll take graphs to be directed unless otherwise specified. Most of the graphs we’ve encountered are best thought of as directed graphs. State transitions in an idealised machine often go in one direction only. Undirected trees are sometimes useful but most of our trees, e.g. abstract syntax trees or trees representing possible paths for a non-deterministic computation, have a natural direction to their edges, from parent to child. There is no real loss of generality in considering graphs to be directed. We can always think of an undirected graph as a special case of a directed graph where for each edge from on vertex to another there is a corresponding edge in the reverse direction. It’s linguistically a bit unfortunate that undirected graphs are directed graphs but a lot of mathematical terminology has similar properties. The only real disadvantage of this point of view is that you have to be careful reading works which deal only with undirected graphs. They will use the word edge to refer to what we’re considering a pair of edges. Later we’ll consider Eulerian paths in an undirected graph, for example. In a text devoted solely to undirected graphs these would usually be described as traversing each edge exactly once. If you’re considering undirected graphs as directed graphs then you need to modify this to say that a path is Eulerian if from each pair of oppositely directed edges it traverses one edge exactly once and the other not at all. To avoid clutter in diagrams, whenever we have an undirected graph I will show a single edge without arrows rather than a pair with arrows, as I did in the first and third examples above. That convention is limited to undirected graphs however. For graphs which are not undirected I will show both edges where there are two.
I will allow infinite graphs, but will restrict attention to finite graphs wherever that’s convenient. The graphs associated to finite state automata, abstract syntax trees, and computational paths of processes guaranteed to terminate are all finite. The tree of computational paths of a non-terminating process is infinite.
I will allow self loops in the definition, because they arise naturally in graphs for finite state automata. For some theorems though it will be necessary to add a hypothesis that the graph has no self loops.
I’ll exclude the possibility of having more than one edge from one vertex to another. This means that for a finite state automaton where there is more than one input token which causes a given transition we need to list all of those in the label on a single edge rather than having multiple edges each labelled by a different token. Note that the restriction is only on multiple edges from one vertex to another. We are allowed to have two edges between a pair of edges as long as they go in different directions.
The choices above are motivated mainly by applications to the theory of computation. Graph theorists tend to make a different set of choices, preferring undirected finite graphs with no self loops.