Original post by megafobia
Using induction on |G|
Any help would be appreciated.
Don't know if I can help, but it would be useful to know what "e|G|" is. ?
Original post by ghostwalker
Don't know if I can help, but it would be useful to know what "e|G|" is. ?
It was a typo. Sorry.
Original post by megafobia
It was a typo. Sorry.
so it's the number of edges.And what's the restriction on G? Simple? Multiple edges between two vertices? Loops allowed? I presume it's undirected.
Edit: It would also help to know your definition of a cycle.
(edited 8 years ago)
Original post by megafobia
...
I'm asking you the above questions as there are various types of graphs, and the meaning of terms varies.
My last post on this thread:
In your induction step, for the graph with n+1 vertices, treat the cases where the minimum degree of the vertices is 0, 1, >1 separately.
Will probably work - without knowing what your definitions are.
In your induction step, for the graph with n+1 vertices, treat the cases where the minimum degree of the vertices is 0, 1, >1 separately.
Will probably work - without knowing what your definitions are.
(edited 8 years ago)
Original post by ghostwalker
My last post on this thread:
In your induction step, for the graph with n+1 vertices, treat the cases where the minimum degree of the vertices is 0, 1, >1 separately.
Will probably work - without knowing what your definitions are.
In your induction step, for the graph with n+1 vertices, treat the cases where the minimum degree of the vertices is 0, 1, >1 separately.
Will probably work - without knowing what your definitions are.
Original post by Raiden10
...
Do see the forum guidelines on posting full solutions - sticky at top of forum.
Original post by ghostwalker
Do see the forum guidelines on posting full solutions - sticky at top of forum.
Notwithstanding I refuse to believe that anyone is going ever to learn proof by induction without having multitudes of complete proofs by induction thrown at them.
Giving hints and asking beginning students of "proof" to realise what took mathematicians quite some amount of time to properly formalize seems rather optimistic.
There aren't probably any results in graph theory more fundamental than this, so it seems strange in the extreme to leave it as an exercise. I also feel it's not really possible to simplify the proof very much, so ability to give hints is limited, by the short length of the proof.
(edited 8 years ago)
Quick Reply
Related discussions
- UKMT senior challenge
- Recursion Q
- To or to not take Maths (and what to do if i don't)
- Fun top secret info, Spread to your friends/try the first three
- Proof by induction - general question - why prove n=1 works?
- IBDP Math AI HL IA
- Algebra help for proof by induction
- Question on proof by induction for Inductive Sequences
- Edexcel igcse maths topics
- Core pure maths Series question
- Ocr mei unofficial markscheme a level (paper 1 2023)
- Arctic shores PWC - Aptitude Test
- 2022 Edexcel Maths GCSE (Higher) Checklist
- edexcel further maths core pure paper 1
- Proof by induction question
- Edexcel AS Level Further Maths 2022
- Proof by induction question
- CIE A Level Computer Science Sucks!
- Tesco induction
- Physics Magnetic fields
Latest
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
