Regular graph

A graph is $d$-regular when every vertex has degree $d$.

Let $p$ be prime and set $s=2p-2$. If a bipartite graph has edge-disjoint perfect matchings $M_0,\dots ,M_{\sigma -1}$ on nested nonempty vertex sets, and $|V(M_{i+s})|>s|V(M_i)|/(s+1)$, then the union of $s+1$ consecutive matchings in a graph has maximum degree at most $2p-1$ and more than $(p-1)|V(M_i)|$ edges. The prime-regular subgraph from Boolean polynomial constraints gives a $p$-regular subgraph. Its perfect matching decomposition gives a $k$-regular subgraph for every $k\le p$. If none exists, every $s$ steps shrink the vertex set by factor at most $s/(s+1)$, bounding $\sigma$ by a constant times $\log n$.

For fixed $r,\ell \ge 3$ and $rn$ even, a prescribed graph cycle in the configuration model has two ordered distinct half-edges at each of its vertices. Therefore its expected count is $(n{)}_{\ell }[r(r-1){]}^{\ell }/[2\ell {\prod }_{j=0}^{\ell -1}(rn-2j-1)]$. Conditioning on the chosen cycle leaves degrees $r-2$ at its vertices and $r$ elsewhere; forbid further edges along that cycle. The bounded-degree pairing avoidance estimate changes by $o(1)$, so the simplicity probability conditional on the cycle divided by the unconditional probability tends to one. The displayed expectation therefore holds for the uniform simple graph, not just the unconditioned pairing model.

The graph whose vertices are two-element subsets of a five-element set, with two vertices adjacent when the subsets are disjoint. It has ten vertices, degree three, zero common neighbours for adjacent pairs and one for nonadjacent pairs. Its adjacency matrix of a graph satisfies $A^2+A-2I=J$ and has eigenvalues $3,1,-2$ of multiplicities $1,5,4$.

If $A$ is the adjacency matrix of a $d$-regular graph and $\mathbf{e}=(1,\dots ,1{)}^T$, every row sum of $A$ is $d$, soIf the graph is connected, the $d$-eigenspace is exactly $\mathrm{span}\{\mathbf{e}\}$.

A connected regular graph has exactly two distinct adjacency eigenvalues if and only if it is a complete graph $K_n$ with $n\ge 2$. Its eigenvalues are $n-1$ on the constant vectors and $-1$ on their orthogonal complement.