0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note that this construction produces $K_{k+1}$ at the $k$th step. $\endgroup$
    – hardmath
    Sep 4 '14 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.