Graph theory terminology 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 vertices have?
- 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 vertices?
- edges; every degree is .