Is this correct for proof of correctness?

[cinder maple]

Im not really good with these so can someone review my proof of correctness for the algorithm please.

[gray cairn]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules.
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[cinder maple]

Oh shit Im rewatching my lecture and they use induction for proof of correctness

Is that ncecessary?

[feral narwhal]

don't know about necessary but if I had to prove correctness of an algorithm, induction is the first thing I'd think of

[cinder maple]

I see. What do you say about this. I am not rlly confident in my inductive step

[feral narwhal]

You can say the algorithm for a singleton graph, or two-vertex graph for that matter, is obviously correct

and formulate your induction assumption precisely

since that's what you have to invoke during induction

[cinder maple]

Is my current I.H not good enough?

[feral narwhal]

you take a k+1 vertexed graph and pick any one vertex in it, delete it and all edges incident to it, then by induction algorithm is correct (w.e that means) on the k-vertexed graph

[cinder maple]

right

but then what about the +1 vertex

how would I deal with that

[feral narwhal]

you follow the algorithm

that's the whole point of induction

[cinder maple]

oh so basically all of this

for that new vertex

[feral narwhal]

if you don't have a bipartite graph after deleting the vertex (and all edges), then you didn't have bipartite to start with

so you only need to worry about the case when the smaller graph is bipartite

[cinder maple]

so I would have to split this into 2 cases where the k graph could be bipartite and where it couldnt?

[feral narwhal]

yes, the second case is trivial, just make sure your algorithm returns "not bipartite" for that case

[cinder maple]

alright ill redo my inductive step rq and then could you review my inductive step again 😭

How is this

[feral narwhal]

this is true, because every subgraph of a bipartite graph is bipartite, but why does your algorithm return this result?

im afraid this is not good enough

you have defined your algorithm precisely

so you must retrace its steps precisely as well

[cinder maple]

I should explain why G wont be bipartite if G' isnt? is that what you mean?

[feral narwhal]

no that part is clear

but why does the algorithm conclude this as well?

[cinder maple]

Sorry I dont rlly understand this. Are you saying that I should explain every step of the helper function?

[feral narwhal]

play the algorithm out

[feral narwhal]

yes, you can't explain an algorithm is "correct" in some high level language, you must prove it using the description of the algorithm itself

by high level language I mean something like this

"..helper function will explore .."

what does "explore" mean?

in what order?

[cinder maple]

well it returns None if it isnt bipartite right. and if G isnt bipartite then it contains an odd cycle so adding that additional vertex still wont fix the issue of the odd cycle being present in G'?

[cinder maple]

ah right my bad Ill fix that

[feral narwhal]

all that is fine, but why does your algorithm recognise this?

there is no mention of odd cycles anywhere in the pseudocode

[cinder maple]

oh u mean this

because of this condition

the helper returns False

implying there is a conflict right

thats why

@feral narwhal

How is this