Special 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 a simple graph?
- A graph with no loops and no multiple edges.
- State the handshaking lemma.
- number of edges.
- What is a tree?
- A connected graph with no cycles.
- How many edges does a tree on vertices have?
- How many edges does have?
- What is the degree of every vertex of ?
- What is a bipartite graph?
- A graph whose vertices split into two sets so that every edge joins a vertex of one set to a vertex of the other.
- How many edges does have?
- Why does a triangle make a graph non-bipartite?
- Three mutually adjacent vertices cannot be shared between two sets without two of them being in the same set and joined.
- Define the complement of a simple graph .
- Same vertices; two vertices are adjacent in exactly when they are not adjacent in .
- Degree of in the complement?
- What does a row sum of a simple graph's adjacency matrix give?
- The degree of that vertex.
- Properties of the adjacency matrix of a simple graph?
- Entries 0 or 1, zero diagonal, symmetric.