Language and properties of graphs 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 the degree of a vertex?
- The number of edge-ends at the vertex; a loop counts twice.
- What is the sum of the degrees of all vertices?
- Twice the number of edges.
- What is a trail?
- A walk in which no edge is repeated.
- What is a path?
- A walk in which no vertex is repeated.
- What is a cycle?
- A closed path: it starts and ends at the same vertex and repeats no other vertex.
- What does connected mean?
- There is a path between every pair of vertices.
- What is a subdivision of an edge?
- Replacing an edge with a path through a new vertex, which adds one vertex and one edge.
- When is a connected graph Eulerian?
- When every vertex has even degree.
- When is a connected graph semi-Eulerian?
- When exactly two vertices have odd degree.
- Where must a semi-Eulerian trail start and finish?
- At the two odd-degree vertices.
- What is a Hamiltonian cycle?
- A cycle that passes through every vertex exactly once.
- Why can't a vertex of degree 1 be on a cycle?
- A cycle needs two edges at every vertex it passes through.
- How many odd vertices can a graph have?
- An even number, because the sum of degrees is even.