# Graph Theory Induction Proof

Watch
Announcements
#1
Using induction on , show that if then contains a cycle

Any help would be appreciated.
0
5 years ago
#2
(Original post by megafobia)
Using induction on , show that if then contains a cycle

Any help would be appreciated.
Don't know if I can help, but it would be useful to know what "e|G|" is. ?
1
#3
(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.
0
5 years ago
#4
(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.
0
5 years ago
#5
(Original post by megafobia)
...
I'm asking you the above questions as there are various types of graphs, and the meaning of terms varies.
0
5 years ago
#6
What's your base case going to be?
0
5 years ago
#7
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.
0
5 years ago
#8
(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.
PRSOM (Although a phrase involving horses and water comes to mind w.r.t. the OP).
0
5 years ago
#9
(Original post by Raiden10)
...
Do see the forum guidelines on posting full solutions - sticky at top of forum.
0
5 years ago
#10
(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.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Are you travelling in the Uni student travel window (3-9 Dec) to go home for Christmas?

Yes (46)
31.29%
No - I have already returned home (19)
12.93%
No - I plan on travelling outside these dates (30)
20.41%
No - I'm staying at my term time address over Christmas (14)
9.52%
No - I live at home during term anyway (38)
25.85%