First Oral Exam Flashcards
What is a graph?
an ordered pair of sets (V,E).
What is V?
the vertex set
What is E?
the edge set. E contains two element subsets of V.
What is the complement of a graph?
the complement of a graph, denoted G_bar, is a graph with the vertex set V(G), and an edge set defined by:
uv » E(G_bar) iff uv ¬« E(G)
What is a clique?
A SET of pairwise adjacent vertices of a graph
What is an independent set?
A set of pairwise nonadjacent vertices
What is a path?
A graph G with a vertex set {x1, x2, x2, …, xk} such that E(G) = {x1x2, x2x3, …, xk-1xk}
What is a cycle?
A graph G with V(G) = {x1, x2, x2, …, xk} and E(G) = {x1x2, x2x3, …, xk-1xk, xkx1}
How do you denote a path with k vertices?
P_k
How do you denote a cycle with k vertices?
C_k
What is a complete graph?
A graph where all vertices are pairwise adjacent, denoted K_k.
What is a trivial, or null, graph?
A graph with |V(G)| = 0
What is an empty graph?
A graph with |V(G)| ≥ 1, and |E(G)| = 0
What is the order of a graph?
The size of the vertex set
What is the size of a graph?
The size of the edge set.
What is a bipartite graph?
A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets called partite sets ofG.
What is the degree of a vertex?
The degree of a vertex v in a graph G, written d_G(v) or d(v), is the number of edges incident to v.
How do we denote the minimum degree of a vertex in G?
∂(G)
How do we denote the maximum degree of a vertex in G?
∆(G)
How do we denote the average degree of G?
d(G)
What is the distance between vertices u and v?
the minimum length of a u-v path, if one exists. If not it is infinity.
What is the diameter of a graph?
the maximum distance between any two points u and v
How is the distance between vertices u and v denoted?
d(u,v), or d_G(u,v)
How is the diameter of a graph denoted?
max_(u,v »V(G)) d(u,v)
What is the eccentricity of a vertex u?
The maximum distance between u and any other point.
How is the eccentricity of a vertex u denoted?
epsilon(u)
What is the radius of a graph?
The minimum eccentricity of any vertex u, or min_(u
«V(G)) epsilon(u)
What is the girth of a graph?
The length of its shortest cycle.
What is the circumference of a graph G?
The length of its longest cycle
How do we denote the circumference of a graph G?
c(G)
What is the girth and circumference of a graph G with no cycles?
Infinite!
What is a forest?
A graph with no cycles
What is a leaf?
A vertex of degree one in a forest
What is a subgraph?
A subgraph of a graph G is a graph H such that V(H) are a subset of V(G) and E(H) are a subset of E(G).
How do we denote that H is a subgraph of G?
H is a subset of G, and we say that G contains H.
What is an induced subgraph?
If H is a subgraph of G such that H contains all edges uv »E(G) with uv »V(H), then H is called an induced subgraph of G. We often say that V’ is a subset of V(G) induces a subgraph H in G.
What does it mean for a graph to be connected?
A graph is said to be connected if for every pair of vertices u and v there is a path from u to v in G.
What is a disconnected graph?
A graph that is not connected.
What is a component of a graph G?
Each maximal set of vertices that induces a connected subgraph of a graph G.
What is a separating set of vertex cut of G?
A separating set or vertex cut of a graph G is a set S –(G) such that the graph induced by V(G) – S (often this induced subgraph is denoted by G – S) contains more than one component.
What is the connectivity of a graph?
the minimum size of a vertex set S such that G – S contains more than one component or V(G) – S is a single vertex.
How do we denote the connectivity of a graph G?
kah(G)
What does it mean for a graph to be k-connected?
if its connectivity is at least k.
What is the walk of a graph G?
A list v0,e1,v1, …, ek,vk, of vertices and edges such that for 1 ≤ i ≤ k, the edge e_i has endpoints v_(i-1) and vi.
What is a closed walk?
A walk where the starting vertex and the ending vertex are the same.
What is a trail?
A walk with no repeated edges.
What is the degree sequence of a graph?
the list of vertex degrees, usually written in non-increasing order.
What is a graphic sequence?
list of nonnegative numbers that is the degree sequence of some simple graph.
What does it mean for a graph to realize d?
The simple graph has the degree sequence d.
What is the Havel Hakimi Theorem?
A non-increasing sequence of nonnegative integers S: d1, … dp, (p ≥ 2) is graphical if and only if, the sequence S1: d2-1, d_(d1+1)-1;, d_(d1+2), …, dp is graphical.
How can you prove the Havel Hakimi Theorem?
Assume S is a graphical sequence, and that the sum of the degree of the vertices adjacent to v_1 is maximum.
1) If the vertices adjacent to v_1 have degrees of d_2, d_3, etc, then the result is obvious.
2) There must exist two vertices then, which one has greater degree than the other, and the one with smaller degree is adjacent to v_1, and the one with higher degree not. These two could switch edges then, maintaining their degree. But v_1 would have more neighbors of higher degree! But that would mean that the sum of the degrees of the vertices in our sequence wasn’t maximum before, a contradiction.
QED.
What is isomorphic?
Two graphs G and H are said to be isomorphic if there exists a bijection f:V(G) -≥ V(H) such that uv«E(G) if and only if f(u)f(v)«E(H). The bijection is often referred to as an isomorphism.
What does it mean for a graph to be H-free?
A graph G is H-free if G has no subgraph isomorphic to H
What is a matching?
A set of edges that share no endpoints
What is a saturated vertex?
A vertex that is incident to an edge in a given matching.
What is a perfect matching?
A matching that saturates every vertex in a graph.
What is a maximum matching?
A matching of the largest size
What is a maximal matching?
A matching that cannot be larger because of how it is placed.
What is a M-alternating path?
A path that alternates between edges in the matching and edges not in the matching
What is an M-augmenting path?
A M-alternating path where both endpoints are unsaturated by M.
What is the disjoint union of G and H?
A graph in which V(G) U V(H) and E(G) U E(H)
What is the symmetric difference of G and H?
A subgraph of G U H, whose edges are the edges of E(G) U E(H) appearing in exactly one of G and H.
How do you denote the symmetric difference?
G∆H
Every component of the symmetric difference of two matchings is…
a path or a cycle
What is Berge’s Theorem?
A matching M in a graph G is a maximum matching in G iff G has no M-augmenting path.
What is Hall’s Theorem?
An bipartite graph G with parts X and Y has a matching that saturates X if and only if |N(S)| ≥ |S| for all S within X.
All trees are_____, have _____ edges, and contain _____.
connected,
n-1,
no cycles.
