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 whose vertices are the set of all lists of length four with items a, b, c, and d, i.e. the same vertices as in the example above, but with edges from each vertex to every other vertex. This is a \({ K _ { 1 2 } }\). The graph considered earlier, which we saw was a \({ K _ { 6 , 6 } }\), is a subgraph of it. More generally, any \({ K _ { p , q } }\) is a subgraph of \({ K _ { p + q } }\).
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.
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.