Special graphs
The families of graphs to know: complete, chain, cycle, star, tree, bipartite, regular, planar, weighted, directed acyclic, complement and subgraph.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Complete graph Kₙ: what is it?
Show the answer
A structure on n vertices in which every pair of distinct vertices is joined by an edge.
It has n(n − 1)/2 edges, the maximum for a simple graph of order n, and every vertex has degree n − 1.
Which of these graphs is bipartite?
- The cycle C₆
- The cycle C₅
- The complete graph K₃
- The complete graph K₄
Show the answer
The cycle C₆
C₆ alternates two colours: 1, 2, 1, 2, 1, 2 and the loop closes onto a different colour. C₅, K₃ and K₄ contain a triangle or a cycle of length 5, an odd length.
The complete graph Kₙ has … edges.
Show the answer
The complete graph Kₙ has n(n − 1)/2 edges.
Each vertex has n − 1 neighbours, so n(n − 1) ends, and each edge has two: divide by 2.
Bipartite graph: what is it?
Show the answer
A structure whose vertices split into two groups, with no edge inside a single group.
Equivalent: it can be coloured with two colours, or it has no odd-length cycle. Agent-to-task assignments are examples.