3033: CHAPTER 1: BASIC NOTIONS Flashcards
Definition of a graph
A graph is a pair of sets G=(V,E) such that E ⊆ V^{2}
What is A^{2}?
The set of 2 element subsets of A
What is the maximum number of vertices for a graph of n vertices?
(n 2) = n!/2!*(n-2)!
For 2<=k
It is the graph whose vertices are the k-element subsets of {1,…,n} with two k-subsets adjacent if they intersect in a (k-1)-subset
What does it mean for 2 vertices to be adjacent?
There is an edge between them
When are two vertices u and v neighbours?
When there is an edge between them
What does it mean for a vertex v to be incident to an edge e?
The edge e has an endpoint at v
What is the d(v)?
The number of edges incident to v
When is a vertex isolated?
When it has degree 0
What is the handshaking lemma?
SUM (i=1 n)(d(xi)) = 2|E|
For a graph G=(V,E), what is a subgraph?
A graph G’=(V’,E’) where V′⊆V and E′⊆E.
When is a subgraph a spanning subgraph?
When V’=V
When is a subgraph an induced subgraph?
When for all u,v ∈ V′, if uv ∈ E then uv ∈ E′.
When is a graph G complete?
When there is an edge between any two vertices
When is a graph G null?
When it has no edges
Let G = (V,E) be a graph. What is a bipartition of G?
It is a pair of subsets X,Y ⊆ V such that X ∪ Y = V, X ∩ Y =∅ and every edge of G has one endpoint in X and the other in Y
When is G complete bipartite
If it has a bipartition X , Y such that every vertex in X is adjacent to every vertex in Y .
Let G be a graph. For k ∈ N, what does it for G to be k-regular?
All the vertices of G have degree k.
Let G = (V,E) be a graph. For a subset V′ ⊆ V, what is G −V′?
It is the graph obtained from G by deleting the vertices in V ′ and deleting all edges incident with them
Let G = (V,E) be a graph. For a subset E′ ⊆ E, what is G−E′?
It is the graph obtained from G by deleting the edges in E′?
Let G = (V , E ) be a graph. What is the complement of G?
It is the graph Gc = (Vc, Ec), where Vc =V and Ec = V^{2}\E
Let G = (V,E) and G′ = (V′,E′) be graphs. What is an isomorphism f : G → G′ ?
It is a bijective function f : V → V′ such that u and v are adjacent in G if and only if f(u) and f(v) are adjacent in G ′ , for all u , v ∈ V .
If G ∼= H then what can we say about Gc and Hc
Gc ∼= Hc.
What is an automorphism?
It is an isomorphism of a graph G to itself
Let G = (V , E ) be a graph. When is G vertex-transitive
When if for any u, v ∈ V, there is an automorphism α: G → G with α(u) = v.
If G is vertex-transitive graph. Then what can we say about it?
(i) G is regular
(ii) the complement Gc of G is also vertex-transitive
What is an edge sequence of G?
It is a sequence of vertices
v0 v1 … vk
such that v0v1,v1v2,…vk−1vk ∈ E.
What is a path?
It is an edge sequence where all the vertices in it, except possibly its initial and final vertex, are distinct.
Let G = (V,E) be a graph. For u,v ∈ V, what is d(u,v)?
It is the length of the shortest path from u to v
If there is no path between u and v what is d(u,v)?
∞
What is the diameter of G?
max{d(u,v) | u,v ∈ V}
Let G = (V,E) be a graph and u,v ∈ V. Then what can we say about uv-edge sequences and uv-paths?
Every uv-edge sequence contains a uv-path
What does it mean for an edge sequence to be closed?
It’s initial and final vertex are the same
What is a cycle?
A closed path
What is the birth of G?
The length of the shortest cycle in G
What does it mean for G to be connected?
If for any two vertices u, v of G there is a path from u to v.
Let G = (V,E) be a graph. When is an edge e ∈ E a bridge?
if removing e from G disconnects the graph, i.e. G − e is disconnected
What is a connected component of G
It is a maximal connected subgraph of G
Let G = (V , E ) be a graph with n vertices and k edges. What can we say if G connected
k ≥ n − 1
What is a forest?
A graph with no cycles
What is a tree?
A connected graph with no cycles
Given a tree T, what is a leaf?
A vertex of degree 1
What can we say about a tree with n ≥ 2 vertices.
i) G has at least two leaves.
(ii) If v is a leaf, then G −v is a tree with n−1 vertices.
Let G be a graph with n ≥ 1 vertices. Then the following conditions are equivalent to G being a tree?
(ii) G has no cycles and has n − 1 edges.
(iii) G is connected and has n − 1 edges.
(iv) G is connected, and every edge is a bridge.
(v) each pair of vertices in G is connected by a unique path.
(vi) G has no cycles, but adding any one edge creates a cycle.
Let G = (V,E) be a graph. When is G an Eulerian graph?
If G has an Eulerian tour, i.e. a closed edge sequence that contains every edge of G exactly once.
If every vertex of a graph has degree of at least 2, what can we say about it?
G has a cycle
Let G be a connected graph. When is G Eulerian?
Iff every vertex has even degree
