Nerdygeek12
Badges: 5
Rep:
?
#1
Report Thread starter 1 month ago
#1
A directed Hamiltonian path on
such a graph is a path that visits every vertex precisely once and traverses edges in the correct
direction. A circuit with the same properties is called a directed Hamiltonian circuit.

Show that every directed complete graph has a directed Hamiltonian path.

Please can anyone give me ideas?
0
reply
spaghettifiend1
Badges: 8
Rep:
?
#2
Report 1 month ago
#2
Pick a vertex x and partition the others into sets according to whether edges go into x or out of x, apply induction
0
reply
Nerdygeek12
Badges: 5
Rep:
?
#3
Report Thread starter 1 month ago
#3
(Original post by spaghettifiend1)
Pick a vertex x and partition the others into sets according to whether edges go into x or out of x, apply induction
Could you explain the induction I'm confused?
0
reply
spaghettifiend1
Badges: 8
Rep:
?
#4
Report 1 month ago
#4
(Original post by Nerdygeek12)
Could you explain the induction I'm confused?
I dont want to give it away completely, but I will clarify that you want to use *strong* induction, and you'll be using the vertex x kind of like a bridge to travel between the 2 parts of our partition.
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 tempted to change your firm university choice on A-level results day?

Yes, I'll try and go to a uni higher up the league tables (42)
27.1%
Yes, there is a uni that I prefer and I'll fit in better (14)
9.03%
No I am happy with my choice (88)
56.77%
I'm using Clearing when I have my exam results (11)
7.1%

Watched Threads

View All