megafobia
Badges: 7
Rep:
?
#1
Report Thread starter 5 years ago
#1
Using induction on |G|, show that if e(G)\geq|G| then G contains a cycle

Any help would be appreciated.
0
reply
ghostwalker
  • Study Helper
Badges: 17
#2
Report 5 years ago
#2
(Original post by megafobia)
Using induction on |G|, show that if e|G|\geq|G| then G 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
reply
megafobia
Badges: 7
Rep:
?
#3
Report Thread starter 5 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 17
#4
Report 5 years ago
#4
(Original post by megafobia)
It was a typo. Sorry.
:cool: 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
reply
ghostwalker
  • Study Helper
Badges: 17
#5
Report 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
reply
BlueSam3
Badges: 17
Rep:
?
#6
Report 5 years ago
#6
What's your base case going to be?
0
reply
ghostwalker
  • Study Helper
Badges: 17
#7
Report 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
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 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
reply
ghostwalker
  • Study Helper
Badges: 17
#9
Report 5 years ago
#9
(Original post by Raiden10)
...
Do see the forum guidelines on posting full solutions - sticky at top of forum.
0
reply
Raiden10
Badges: 17
Rep:
?
#10
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All
Latest
My Feed