Graph types and Eulerian 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.
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; vertices and 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 ?
- What is the degree of every vertex in ?
- 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.