Mathematics

Graph-theory sketch

Vertices and edges, degree, paths, Euler, and the adjacency matrix.

Basics

Graphs

Vertices (nodes) and edges draw relations. Undirected edges go both ways; directed ones have arrows. Simple versus multi graphs depend on loops and parallel edges. Weights are distance or cost. Maps, networks, and molecules share the language. The drawing is a model, not the whole reality.

Degree and handshaking

Degree is how many edges meet a vertex. Summing degrees counts each edge twice (handshaking lemma). So the number of odd-degree vertices is even. A regular graph has one common degree. Directed graphs split in- and out-degree. That one line starts many existence proofs.

Paths and Euler

A path is a walk along edges. An Euler circuit traverses every edge once in a connected graph and exists when no vertex has odd degree — the Königsberg answer. A Hamilton path visits every vertex once and is much harder to guarantee. Shortest paths bring weights and algorithms such as Dijkstra.

Adjacency matrix

Rows and columns are vertices; an edge stores 1 (or a weight). Entries of A² count walks of length 2. The Laplacian L = D − A leads into spectral graph theory. Sparse graphs prefer adjacency lists in memory. It is how computers read the picture as numbers.

Formulas

Handshaking

Σ deg(v) = 2 |E|

There are evenly many odd-degree vertices.

Symbols

|E| number of edges
deg(v) degree of vertex v

Euler-circuit condition

연결 + 홀수 차수 0개

Undirected. An Euler trail (not closed) needs 0 or 2 odd degrees.

Adjacency square

(A²)_{ij} = (i→j 길이 2 보행 수)

For a simple undirected unweighted graph.

Symbols

A adjacency matrix

Key table

Tree	connected and acyclic; \|E\| = \|V\| − 1
Bipartite	split vertices into two sides; edges only between sides
Complete graph K_n	every pair joined; \|E\| = n(n−1)/2