hi i'm reading a book about theory of computation by Michael sipser, and i'm a little confused by one of the proofs of a simple theorem.
was wondering if anybody could help me understand the method of working out. Or if they could just answer maybe one instance of the case and i could work backwards myself.
theorm
for each even number n greater than 2, there exists a 3-regular graph with n nodes
proof
let n be an even number greater than 2. construct graph G=(V,E) with n nodes as follows the set of nodes of G is V={0,1...n-1) and the set of edges of G is the set
(part i need help with)
E={{i,i+1}|for 0 ≤ i ≤ n-2} U {{n-1,0}} U {{i,i+n/2}|for 0 ≤i ≤ n/2 -1 }.
my confusion
so i understand that v is the nodes and E is supposed to show which edges connect with the node and i know how to draw the graph and what a 3 regular graph is and i even know the theorem is true i guess i'm just doing the maths incorrectly since whenever i try to work it out i seem to be getting wrong pair/edges. thanks
"Algebraically" (that is, without drawing diagrams), what's going is that the first part of the edge set, $$ \{ \{i,i+1\} : 0 \le i \le n-2\} \cup \{\{0,n-1\}\}, $$ provides degree $2$ to each vertex. A vertex $i$ with $0 < i < n-1$ is incident to edges $\{i-1,i\}$ and $\{i,i+1\}$. The vertex $0$ is incident to edges $\{0,1\}$ and $\{0,n-1\}$, and the vertex $n-1$ is incident to edges $\{n-2,n-1\}$ and $\{0,n-1\}$.
The second part of the edge set, $$ \{\{i,i+n/2\} : 0\le i \le n/2-1\}, $$ adds $1$ to the degree of each vertex, for a total of $3$. A vertex $i$ with $0 \le i \le n/2-1$ is incident to the edge $\{i,i+n/2\}$; a vertex $i$ wtih $n/2 \le i$ is incident to the edge $\{i - n/2, i\}$.
Alternatively, using modular arithmetic, each vertex $i$ is adjacent to the three vertices $$ \{(i-1) \bmod n, (i+1) \bmod n, (i+n/2) \bmod n\} $$ making this a $3$-regular graph.
Graphically ("graph" being Greek for "picture", after all), if you draw the vertices $0, 1, \dots, n-1$ in order around a circle, the graph diagram you get will look like this:
(Just to be clear, there is no vertex in the center of the circle; there's just something that looks kinda like a dot because a whole lot of lines intersect there.)
The edges $\{i,i+1\}$ for $i=0,1,\dots,n-2$, as well as the edge $\{0,n-1\}$, go around the boundary of the circle. The edges $\{i,i+n/2\}$ for $i=0,1,\dots,n/2-1$ are the "diameter" edges that go to the opposite vertex on the circle.
This graph is $3$-regular because each vertex is adjacent to the two neighbors around the circle as well as the vertex opposite from it on the circle: three vertices in total.