نظریهٔ گراف
Graph Theory
مباحث نظریهٔ گراف.
ریاضیات گسسته کنکور ارشد علوم کامپیوتر
کارتها · 15
An edge is a bridge exactly when it lies on no cycle, so a bridgeless graph is one in which every edge sits on some cycle.
The number of walks of length k from i to j is the (i,j) entry of A^k ; length- 2 paths come from counting neighbor-pairs per vertex.
When vertices are the k -subsets of an n -set and edges encode a fixed intersection size, the graph is automatically regular, and its degree and edge count fall straight out of binomial counting.
Pairwise-distinct edge weights force a single MST; uniqueness fails exactly when some cycle has a non-unique heaviest edge (a tie), so ties — not the cheapest edge — decide the count.
Each rung pair holds at most one vertex, so a large independent set fixes which columns are used; the empty columns cut the rest into paths, and every path contributes a factor of 2 (outer/inner must alternate).
The hypercube Qn connects n-bit strings (or subsets of an n-set) that differ in one bit; it is n-regular and bipartite, and for n >= 1 always has a perfect matching and a Hamiltonian cycle (n >= 2).
A tree has at most one perfect matching (uniqueness, via the acyclic symmetric-difference argument); and any graph on 2n vertices with minimum degree ≥ n has a perfect matching (existence, Dirac-type).
Every simple planar graph on n ≥ 3 vertices has at most 3n−6 edges — a direct consequence of Euler's formula, and an instant non-planarity test.
Key lower and upper bounds on the chromatic number χ(G) : the independence-number lower bound χ ≥ n/α , greedy degree-based upper bounds, and the minimum-degree property of color-critical graphs.
The exact number of spanning trees is any cofactor of the Laplacian (Matrix-Tree), but for graphs glued at cut vertices the count simply multiplies block by block — a cycle of length k contributes a factor of k.
If G is Hamiltonian then deleting any set S of vertices leaves at most S connected components: c(G-S) ≤ S . Deleting many vertices and counting components that shatter is the fastest way to prove a graph is NOT Hamiltonian.
The sum of all vertex degrees equals twice the number of edges — so the number of odd-degree vertices is always even, and many "does this graph exist?" questions collapse to one parity/counting check.
Sweep a linear (chain-like) graph left to right; the only state that crosses each cut is whether the boundary vertex is already matched, giving a small linear recurrence you solve like a Fibonacci.
Vertex connectivity, edge connectivity, and minimum degree obey κ(G)≤λ(G)≤δ(G) ; Menger's theorem recasts connectivity as a max number of disjoint paths, and cubic graphs force κ=λ .
The path Ramsey number R(P_m,P_n) — the least N so every red/blue coloring of K_N has a red P_m or blue P_n — has the closed form R(P_m,P_n)=m+⌊ n/2⌋-1 for m≥ n≥ 2 ; e.g. R(P_4,P_4)=5 .