Suppose we have a graph with vertex set \({ V }\) and edge relation \({ E }\). If \({ W }\) is a subset of \({ V }\) and \({ F }\) is a subset of the restriction of \({ E }\) to \({ F }\) then we say that the with vertex set \({ W }\) and edge relation \({ F }\) is a subgraph of the one with vertex set \({ V }\) and edge relation \({ E }\). Note that in cases where two vertices \({ x }\) and \({ y }\) in \({ W }\) are connected by an edge in \({ F }\) they are required to be connected by an edge in \({ E }\), but not vice versa. We could, for example, obtain a subgraph by keeping all the vertices and removing all the edges, although this wouldn’t be particularly interesting. For a slightly more interesting example, consider the graph with 14 vertices considered earlier. It can be considered as a subgraph of \({ K _ { 7 , 7 } }\), since we could add further edges between each even numbered vertex and each odd numbered vertex.
Like many concepts in graph theory, the notion of a subgraph is related to graph homomorphisms. If \({ V }\) is a subgraph of \({ W }\) then the inclusion function from \({ V }\) to \({ W }\), i.e. the one defined by \({ g ( a ) = a }\) for all \({ a ∈ V }\), is a graph homomorphism.
The in-degree of a vertex in a graph is the number of edges from that vertex while the out-degree is the number of edges to that vertex. In undirected graphs these two numbers must be the same and are just called the degree of the vertex. Corresponding vertices in isomorphic graphs have the same in-degrees and have the same out-degree. This can be used to show that a pair of graphs are not isomorphic, by showing that the number of vertices with a given in and out degree differ between the two graphs.
Degrees are generally only useful when they’re finite. This is certainly the case for finite graphs but it is possible to have an infinite graph where all the vertices have finite degree.
An undirected graph where all vertices have the same degree is called regular. Complete graphs are always regular. A \({ K _ { p , q } }\) is regular if and only if \({ p = q }\). The EU borders graph considered earlier is very far from regular. There are some vertices, e.g. Ireland, with degree 0 while Germany has degree 8. An example of a regular graph which is not a \({ K _ n }\) or \({ K _ { p , p } }\) can be found in the accompanying figure, where each vertex has degree 5.
Each edge goes from on vertex to another. If we group the edges by their initial endpoints then the number for each vertex is its out-degree, so the number of edges is equal to the sum of the out-degrees of the vertices. Similarly, if we group them by their final endpoints then we see that the number of edges is equal to the sum of the in-degrees of the vertices. The sum of the in-degrees is therefore equal to the sum of the out-degrees.
For an undirected graph the in-degrees and out-degrees are the same, so we can just say that the sum of the degrees is equal to the number of edges. We have to be careful here though, because edges occur in pairs an our convention is to draw only one of each pair. The sum of the degrees is therefore twice the number of edges visible in the diagram. This is always an even number so we obtain the useful result that the sum of the degrees of the vertices in an undirected graph is always and even number, and the corollary that the number of vertices of odd degree is even.