Back to Discover
🔢

Vertex cover

math Maturity 11-13

Imagine some dots with lines between them.

Vertex-cover.svg
Vertex-cover.svg
We want to pick some dots. We must pick dots to touch every line. This helps us cover the whole shape. We try to use as few dots as we can. Can you find the best dots?
Minimum-vertex-cover.svg
Minimum-vertex-cover.svg

46 words
🖼️ Images & Media (4)
File:Couverture de sommets.svg
Couverture de sommets.svg
File:Vertex-cover.svg
Vertex-cover.svg
File:Minimum-vertex-cover.svg
Minimum-vertex-cover.svg
File:Vertex-cover-from-maximal-matching.svg
Vertex-cover-from-maximal-matching.svg
Up Next
🔢
Edge cover
Math
→
More to explore

✨ What else?

Related topics you might enjoy

Edge cover 0% Clique problem 0% Clique (graph theory) 0% Kőnig's theorem (graph theory) 0% NP-hardness 0% Maximum-cardinality matching 0%

🔬 Go deeper

More advanced topics to explore

NP-hardness Matching (graph theory) Graph isomorphism problem Bipartite graph

🪜 Step back

Simpler topics to build understanding

Edge cover Clique problem Clique (graph theory) Kőnig's theorem (graph theory)
📚 Content adapted from Wikipedia | Readability: FK 12.5 | Vital Level 5