# Graph theory

Watch
Announcements
#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
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
#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
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
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 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%