Graph types and Eulerian graphs

Graph types and Eulerian graphs Flashcards

Spec 1.3 · 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.

14 cards

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

See all 14 cards
What is the order (degree) of a vertex?
The number of edges meeting at that vertex.
What is the sum of the degrees in a graph?
Twice the number of edges.
Define a tree.
A connected graph with no cycles; nn vertices and n−1n-1 edges.
Define a spanning tree.
A subgraph that is a tree and includes every vertex of the graph.
What is a cycle?
A closed path that starts and ends at the same vertex and visits no other vertex twice.
What is a digraph?
A graph whose edges have directions, shown by arrows.
How many edges has KnK_n?
n(n−1)2\frac{n(n-1)}{2}
What is the degree of every vertex in KnK_n?
n−1n-1
When is a graph planar?
When it can be drawn with no edges crossing.
What does isomorphic mean for two graphs?
A one-to-one matching of vertices that preserves every edge.
Condition for a connected graph to be Eulerian?
Every vertex has even degree.
Condition for a connected graph to be semi-Eulerian?
Exactly two vertices have odd degree; the trail runs from one to the other.
What if a connected graph has four odd vertices?
It is neither Eulerian nor semi-Eulerian.
Why can a graph never have exactly one odd vertex?
The degree sum is twice the number of edges, which is even, so odd vertices come in pairs.

Flashcards