Graphs

Definition: Graph, vertex, edge

A graph is a pair where is a finite set whose members are called vertices and is a set of -subsets of whose members are called edges.

Definition: Adjacent, neighbour

Two vertices and of a graph are adjacent or neighbours whenever .

Definition: Isomorphic graphs

Two graphs and are isomorphic if there exists a bijection such that for every . In this case, is called an isomorphism from to .

Determining if two graphs are isomorphic is nontrivial, but two graphs can quickly be shown not to be isomorphic if for example they have a different number of vertices or edges.

Definition: Degree of vertex

Let be a graph and . Then and the degree of is , or in other words, the number of edges containing .

So then of course, the multiset of degree counts of two isomorphic graphs must be the same, meaning this is another fast way of determining that two graphs are not isomorphic.

Theorem

Let be a graph. Then Proof:
Each edge is counted twice; once for each vertex in the edge. In other words,

Definition: Odd vertex, even vertex

A vertex is odd if its degree is odd, or even if its degree is even.
Given a graph we define

This makes a partition of .

Theorem: The number of odd vertices is even

Let be a graph. Then is even.

Proof:
We know that both and are even, and we also know meaning must also be even. But it's a sum of odd numbers, meaning it must be a sum of an even number of odd numbers.

Definition: Regular graph

A graph in which all vertices have the same degree is said to be regular with degree .

In the case of regular graphs, we thus see that .