The planarity algorithm and Hamiltonian cycles

The planarity algorithm and Hamiltonian cycles Flashcards

Spec 1.4 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 13 cards
Define a Hamiltonian cycle.
A cycle that passes through every vertex once and only once and returns to its start vertex.
How many edges does a Hamiltonian cycle of a graph with nn vertices have?
nn
Eulerian cycle versus Hamiltonian cycle?
Eulerian: every edge exactly once. Hamiltonian: every vertex exactly once.
Can a tree have a Hamiltonian cycle?
No: a tree has no cycles.
What is a planar graph?
A graph that can be drawn with no edges crossing.
Which graphs does the planarity algorithm start from?
A graph with a Hamiltonian cycle, drawn as a closed loop.
What is a chord in the planarity algorithm?
An edge of the graph that is not in the Hamiltonian cycle.
When do two chords conflict?
When their end points alternate around the cycle, so they cannot both be on the same side.
Do chords that share a vertex conflict?
No.
Where must two conflicting chords be drawn?
On opposite sides of the cycle: one inside, one outside.
When does the planarity algorithm show a graph is non-planar?
When a chord conflicts with chords on both sides, so it has nowhere to go.
Is K4K_4 planar? Is K5K_5 planar?
K4K_4 is planar. K5K_5 is not planar.
What is a route that visits every vertex once but does not return to the start?
A Hamiltonian path, not a Hamiltonian cycle.

Flashcards