Term
Every u,v walk contains ... 

Definition


Term
An edge is a cut edge iff... 

Definition


Term
Every closed odd walk contains... 

Definition


Term
A graph is bipartite iff... 

Definition


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


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


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 cutvertices. 


Term
In an even graph, every nonextendible trail... 

Definition


Term
For a connected nontrivial 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


Term
Average vertex degree of a graph: 

Definition


Term
Every graph has an even number of vertices of... 

Definition


Term
a kregular graph with n vertices has ____ edges 

Definition


Term
a kregular 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


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


Term

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


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


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 Maugmenting path. 


Term
An X,Ybigraph G has a matching that saturates X iff... 

Definition
...N(S) >= S for all S in X 


Term
For k > 0, every kregular bipartite graph has... 

Definition


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


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 1factor 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
min_{S C= V(G)}{n(G)  [o(G  S)  S]} 


Term
Every 3regular graph with no cutedge has... 

Definition


Term
Every regular graph with positive even degree has... 

Definition


Term

Definition


Term
The minimum number of edges in a kconnected graph on n vertices is... 

Definition


Term
Relationship between connectivity, edge connectivity and minimum degree of G 

Definition


Term
If G is a 3regular graph then... 

Definition


Term

Definition
[Σ_{v in S}d(v)]  2e(G[S]) 


Term
A graph G having at least 3 vertices is 2connected iff ... 

Definition
... for each pair u,v in V(G) there exist internally disjoint u,vpaths in G 


Term
If G is kconnected and G' is obtained by adding a new vertex with at least k neighbors in G, then... 

Definition


Term
For a graph with at least 3 vertices these conditions are equivalent: 

Definition
A) G is connected and has no cutvertex
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 2connected, then the graph G' obtained by subdividing an edge of G is... 

Definition


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 edgedisjoint x,y paths 


Term
Deletion of an edge reduces connectivity... 

Definition


Term
If x,y are vertices of a graph G and xy is not an edge, then the minimum size of an x,ycut... 

Definition
...equals the maximum number of pairwise internally disjoint x,y paths 


Term
If P is an faugmenting 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


Term
The maximum value of a feasible flow... 

Definition
equals the minimum capacity of a source/sink cut. 

