Graph theory terminology

Graph theory terminology Flashcards

Edexcel International A Level 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
What is a graph?
Vertices (nodes) joined by edges (arcs).
What is a weighted graph?
A graph with a number (weight) on each edge, also called a network.
What is the degree of a vertex?
The number of edges meeting at the vertex, also called its valency.
What is the sum of the degrees of a graph?
Twice the number of edges.
How many odd vertices can a graph have?
An even number.
What is a walk?
A finite sequence of edges where the end vertex of one edge is the start of the next.
What is a path?
A walk in which no vertex is repeated.
What is a cycle?
A closed path, starting and ending at the same vertex.
What is a connected graph?
A graph in which every pair of vertices is joined by a path.
What is a tree?
A connected graph with no cycles.
How many edges does a tree with nn vertices have?
n−1n-1
What is a spanning tree?
A subgraph that is a tree and includes all the vertices.
What are the edges and vertex degree in a complete graph on nn vertices?
n(n−1)2\frac{n(n-1)}{2} edges; every degree is n−1n-1.

Flashcards