so I've come across a weird problem. I've learned about induction before, and when it's an equation I can generally do them. However, this problem I'm having trouble with:
"A k-regular graph is an undirected graph where every vertex has degree k. For example, a graph with 3 vertices connected in a triangle is a 2-regular graph, since each vertex has degree 2.
Use induction to show that for every k ≥ 1, there exists a k-regular graph."
I figured I'd give the base step by showing a graph with two points and a single line connecting them to show k = 1. Not really sure where to go from there though or if that's even the case. I'm having a hard time just coming up with a hypothesis for it really. Any direction at all on this will be greatly appreciated it!
Best Answer
It's fine to start there.
To get a $2$-regular graph, starting from $K_2$, we must have at least one more vertex. So, we take $K_2$, add a vertex, then add some edges until we get a $2$-regular graph.
The inductive step is the same process, but for $k$-regular graphs on $k+1$ vertices.
I presume the idea is to teach induction: there's easier proofs of this result, such as observing $K_{k+1}$ or $K_{k,k}$ is $k$-regular.