Graph models, degrees, and isomorphism

A finite simple undirected graph is a pair $G=(V,E)$, where $V$ is a finite vertex set and every edge is a two-element subset of $V$. Thus an edge has distinct endpoints, there is no direction, and a given pair supports at most one edge. Vertices without incident edges still belong to the graph. A drawing is a representation of this data; positions, distances, and crossings do not become mathematical structure unless the model explicitly includes them.

Directed graphs instead use ordered pairs, and multigraphs may distinguish several edges with the same endpoints. A railway model might need parallel edges to record different lines, whereas a friendship model might deliberately merge repeated interactions. Weighted graphs attach additional numbers, such as travel times. Before applying a theorem, check its conventions: the degree formulas below concern undirected graphs, and a loop, if allowed in a different convention, contributes two incidences at its single endpoint.

The degree $d(v)$ counts edges incident with vertex $v$. Add all degrees and inspect a single edge: it appears once at each endpoint, so it contributes exactly two. This gives the handshake identity. In particular the degree sum is even, and the number of odd-degree vertices is even because even summands do not affect parity. These are necessary conditions on a proposed degree list, not a complete test for whether that list is realizable by a simple graph.

For example, the list $(3,3,0,0)$ has an even sum and each entry is at most three, but no simple graph on four vertices realizes it. A degree-three vertex must meet every other vertex, contradicting the two claimed isolated vertices. Local bounds and a global count can both pass while adjacency constraints still fail. This distinction is useful when checking network data: an arithmetic consistency check catches some errors without certifying that the underlying records form the intended graph.

An isomorphism from $G$ to $H$ is a bijection between their vertex sets that preserves adjacency in both directions. Names may change, but the pattern of connections must survive. Vertex count, edge count, the sorted degree list, connectedness, and the presence of triangles are therefore invariants. A mismatch proves that no isomorphism exists. Matching invariants provide evidence worth investigating, but do not replace an actual adjacency-preserving bijection.

A six-cycle and two disjoint triangles both have six vertices, six edges, and six degree-two vertices. They are not isomorphic because the first graph is connected and the second is not. Conversely, two differently drawn four-cycles are isomorphic once their cyclic orders are matched. A reliable proof gives the proposed map and checks every edge and nonedge, or explains why a structural description guarantees both. This is the first example of a recurring strategy: use inexpensive invariants to reject candidates, then construct a witness to establish the positive claim.