Special graphs

Special graphs Flashcards

Spec DA5–DA6 · AQA A-Level Further 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 simple graph?
A graph with no loops and no multiple edges.
State the handshaking lemma.
∑deg⁡(v)=2×\sum\deg(v)=2\times number of edges.
What is a tree?
A connected graph with no cycles.
How many edges does a tree on nn vertices have?
n−1n-1
How many edges does KnK_n have?
n(n−1)2\frac{n(n-1)}{2}
What is the degree of every vertex of KnK_n?
n−1n-1
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 Km,nK_{m,n} have?
mnmn
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 G′G' of a simple graph GG.
Same vertices; two vertices are adjacent in G′G' exactly when they are not adjacent in GG.
Degree of vv in the complement?
n−1−deg⁡G(v)n-1-\deg_G(v)
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.

Flashcards