Let $G=(V,E)$ be a finite, simple, undirected graph. Let $\Delta(G)$ be the maximal degree of $G$. Is there a finite graph $G'=(V', E')$ with the following properties?
- $V\subseteq V'$,
- $E \subseteq E'$, and
- $G'$ is $\Delta(G)$-regular.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $G=(V,E)$ be a finite, simple, undirected graph. Let $\Delta(G)$ be the maximal degree of $G$. Is there a finite graph $G'=(V', E')$ with the following properties?
Yes. First of all, for any vertex $v\in V$ we draw the edges to $\Delta(G)-\deg(v)$ new vertices so that the degree of $v$ becomes equal to $\Delta(G)$. Now all degrees are equal either to $\Delta(G)$ or to 1. Without loss of generality, the number of vertices with degree 1 is even (else add the disjoint copy of the current graph). Partition them onto pairs, and for any pair $a,b$ take a graph $K_{d+1}\setminus \{ab\}$ on the vertex set $\{a,b, d-1\, \text{new vertices}\}$.