MHB Strong induction hypothesis for statement about connected graphs

[find_the_fun]

Use strong induction to prove that if G is connected and every vertex has even degree that G has a Eulerian Circuit.

a)verify the base case where G has no edges - done
b)Write down the strong induction hypothesis that asserts the statement is true for all graphs that meet the hypotheses and have at most k edges.

I'm not sure if I did b right. Here's what I got

Assume that G is connected and it has a Eularian Circuit if has at most k edges and ever vertex has an even degree.
​

Is this right? In the induction hypothesis a new constant is introduced, which is k in this case.

 

[Evgeny.Makarov]

Re: strong induction hypothesis for statement about connected graphs

Assume that G is connected and it has a Eularian Circuit if has at most k edges and ever vertex has an even degree.

First, I would exclude the word "assume" from the hypothesis itself. If the hypothesis is $P(k)$, then the induction step starts with "Assume $P(k)$", and this would make two "assume"s in a row. Second, you need to move "$G$ is connected" to the premise of the assumption. If $P(k)$ has the form "$G$ is connected and (... ⇒ ...)", then, when you are proving $P(k+1)$, you have to prove, in particular, that $G$ with at most $k+1$ edges is connected. Instead, you should assume that it is connected.

Finally, you are right that the hypothesis contains a new variable $k$. What about $G$? There are two options: either $G$ is free in $P(k)$ and is thus the same in $P(k)$ and $P(k+1)$, or it is bound by a universal quantifier. The first case happens when you fix $G$ before starting induction, i.e., when you start the proof by saying "Fix an arbitrary $G$ and then apply a strong induction on $k$". In this case, $G$ is the same throughout the whole induction process. But this does not make sense because $G$ is supposed to have different number of edges. Formally, in proving the induction step $P(k)\implies P(k+1)$, you assume $P(k)$ and the premise of $P(k+1)$, which says that $G$ has at most $k+1$ edges. But then you cannot apply $P(k)$ because its own premise says that the same $G$ has at most $k$ edges. Therefore, you need the second option, where $G$ is universally quantified in $P(k)$.

Altogether, the induction hypothesis $P(k)$ should be as follows: For any graph $G$ with at most $k$ edges, if $G$ is connected and every vertex of $G$ has even degree, then $G$ has a Eulerian circuit.

 

[find_the_fun]

Re: strong induction hypothesis for statement about connected graphs

Ok thanks. The next part asks to explain why the induction hypothesis can be applied to the subgraph H constructed by deleting the edges in the longest circuit in G.

What I don't get is how can you explain the induction step still applies? Isn't it just saying assume something is true, so how could it not apply?

 

[Evgeny.Makarov]

Re: strong induction hypothesis for statement about connected graphs

The next part asks to explain why the induction hypothesis can be applied to the subgraph H constructed by deleting the edges in the longest circuit in G.

What I don't get is how can you explain the induction step still applies? Isn't it just saying assume something is true, so how could it not apply?

Suppose there is a graph $G$ satisfying the premise of $P(k+1)$, i.e., $G$ has at most $k+1$ edges, $G$ is connected and every vertex of $G$ has even degree. Let $G'$ be obtained from $G$ by deleting the edges in the longest circuit. The question asks to show that $G'$ satisfies the premise of $P(k)$, i.e., $G'$ has at most $k$ edges, $G'$ is connected and every vertex of $G'$ has even degree. This way, the conclusion of $P(k)$ applies to $G'$ as well, i.e., $G'$ has a Eulerian circuit, from which we then construct a Eulerian circuit in $G$.

 

[find_the_fun]

Re: Strong induction hypothesis for statement about connected graphs

Ok so I need to show that
1)G' is connected
2)G' has at most k edges
3)Each edge is G' has even degree

I think I'm getting it now.