Question: Something is wrong with this inductive proof. Please identify Proposition. Every graph with at least 2 nodes , and in which all nodes have degree
Something is wrong with this inductive proof. Please identify
Proposition. Every graph with at least nodes and in which all nodes have degree must be connected.
Proof. Let Pnbe the predicate Every graph with exactly n nodes, all of which have degree is connected.We will prove n Pnby induction:
Base Case: Suppose n There is only one node graph in which all nodes have degree which is the graph that has an edge connecting its two nodes. This graph is connected, and so Pholds
Inductive Step: Let n be any integer and assume the inductive hypothesis Pn Let G be a graph with exactly n nodes that all have degree By the inductive hypothesis, G must be connected.
Now add any one new node v to G and one or more edges from v to other nodes in the graph. Call the new graph GNote that Ghas exactly n nodes, and they all have degree Additionally since G is connected and there is an edge from v to a node in Gthere is a path from v to all other nodes. So Gis connected, and so Pnholds
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
