# Shared Flashcard Set

## Details

Graph Theory Theorems
Virginia Tech 5454
51
Mathematics
02/24/2009

Term
 Every u,v walk contains ...
Definition
 a u,v path
Term
 An edge is a cut edge iff...
Definition
 it belongs to no cycle
Term
 Every closed odd walk contains...
Definition
 ...an odd cycle
Term
 A graph is bipartite iff...
Definition
 ...it has no odd cycle
Term
 The complete graph Kn can be expressed as ____ iff ____
Definition
 the union of k bipartite graphs iff n <= 2^k
Term
 If every vertex of a graph G has a degree at least 2...
Definition
 Then G contains a cycle
Term
 A graph G is Eulerian iff...
Definition
 ...it has at most one nontrivial component and its vertices all have even degree.
Term
 Every even graph decomposes...
Definition
 ...into cycles
Term
 If G is a simple graph in which every vertex has degree at least k, then...
Definition
 ...G contains a path of length at least k. If k >= 2, then G also contains a cycle of length at least k + 1.
Term
 Every graph with a nonloop edge has...
Definition
 ...at least two vertices that are not cut-vertices.
Term
 In an even graph, every non-extendible trail...
Definition
 ...is closed.
Term
 For a connected non-trivial graph with exactly 2k odd vertices...
Definition
 ...the minimum number of trails that decompose it is max{k,1}.
Term
 In a graph, the sum of the degrees of all vertices is equal to...
Definition
 2e(G)
Term
 Average vertex degree of a graph:
Definition
 2e(G) / n(G)
Term
 Every graph has an even number of vertices of...
Definition
 ...odd degree.
Term
 a k-regular graph with n vertices has ____ edges
Definition
 nk/2
Term
 a k-regular bipartite graph has...
Definition
 ...the same number of vertices in each partite set
Term
 The minimum number of edges in a connected graph with n vertices is...
Definition
 ...n - 1
Term
 Every loopless graph G has a ____ subgraph with...
Definition
 has a bipartite subgraph with at least e(G)/2 edges
Term
 Every tree with at least two vertices has...
Definition
 ...at least two leaves
Term
 Trees are classified as:
Definition
 connected, acyclic graphs with n - 1 edges, no loops, and for each u,v in V(G) there exists exactly one u,v path.
Term
 If the diameter of a simple graph G >= 3, then the diameter of G complement is...
Definition
 ... <= 3
Term
 If H is a subgraph of G then the distance from u to v in G is ___ the distance from u to v in H.
Definition
 less than.
Term
 What can you tell about the symmetric difference of two matchings?
Definition
 Every component of the symmetric difference of two matchings is a path or an even cycle.
Term
 A matching M in a graph G is a maximum matching iff...
Definition
 ...the graph has no M-augmenting path.
Term
 An X,Y-bigraph G has a matching that saturates X iff...
Definition
 ...|N(S)| >= |S| for all S in X
Term
 For k > 0, every k-regular bipartite graph has...
Definition
 ... a perfect matching.
Term
 What can be said about the maximum size of a matching in a bipartite graph?
Definition
 The maximum size of a matching in a bipartite graph equals that minimum size of a vertex cover.
Term
 In a graph, S is an indepdent set iff...
Definition
 ...S' is a vertex cover
Term
 If G is a graph without isolated vertices then...
Definition
 the maximum size of a matching plus the minimum size of an edge cover equals the number of vertices.
Term
 If G is a bipartite graph with no isolated vertices...
Definition
 ...then the maximum size of an independent set equals the minimum size of an edge cover.
Term
 A graph has a 1-factor iff
Definition
 o(G - S) <= |S| for all S in G
Term
 The largest number of vertices saturated by a matching in G is...
Definition
 minS C= V(G){n(G) - [o(G - S) - |S|]}
Term
 Every 3-regular graph with no cut-edge has...
Definition
 ...a 1-factor
Term
 Every regular graph with positive even degree has...
Definition
 ...a 2-factor.
Term
 κ(Hk,n) =
Definition
 k
Term
 The minimum number of edges in a k-connected graph on n vertices is...
Definition
 ...ceiling[kn/2]
Term
 Relationship between connectivity, edge connectivity and minimum degree of G
Definition
 κ(G) <= κ'(G) <= δ(G)
Term
 If G is a 3-regular graph then...
Definition
 κ(G) = κ'(G)
Term
 |[S, S']| =
Definition
 [Σv in Sd(v)] - 2e(G[S])
Term
 A graph G having at least 3 vertices is 2-connected iff ...
Definition
 ... for each pair u,v in V(G) there exist internally disjoint u,v-paths in G
Term
 If G is k-connected and G' is obtained by adding a new vertex with at least k neighbors in G, then...
Definition
 G' is k-connected
Term
 For a graph with at least 3 vertices these conditions are equivalent:
Definition
 A) G is connected and has no cut-vertex B) For all x,y in V(G) there are internally disjoint x,y paths C) For all x,y in V(G) there is a cycle through x and y D) δ(G) >= 1 and every pair of edges in G lies on a common cycle
Term
 If G is 2-connected, then the graph G' obtained by subdividing an edge of G is...
Definition
 2-connected.
Term
 If x and y are distinct vertices of a graph or digraph then the minimum size of an x,y disconnecting set of edges...
Definition
 ...equals the maximum number of pairwise edge-disjoint x,y paths
Term
 Deletion of an edge reduces connectivity...
Definition
 ...by at most 1.
Term
 If x,y are vertices of a graph G and xy is not an edge, then the minimum size of an x,y-cut...
Definition
 ...equals the maximum number of pairwise internally disjoint x,y paths
Term
 If P is an f-augmenting path with tolerance z...
Definition
 ... then changing the flow by +z on edges followed forward by P and by -z on edges followed backward by P produced a feasible flow f' with val(f') = val(f) + z
Term
 If f is a feasible flow and [S,T] is a source/sink cut then...
Definition
 val(f) <= cap(S,T)
Term
 The maximum value of a feasible flow...
Definition
 equals the minimum capacity of a source/sink cut.
Supporting users have an ad free experience!