Shared Flashcard Set

Details

Graph Theory Theorems
Virginia Tech 5454
51
Mathematics
Graduate
02/24/2009
Click here to study/print these flashcards.

Create your own flash cards! Sign up here.

Additional Mathematics Flashcards

 

 

Cards

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!