Final Flashcards
Graph
A graph is a pair G = (V; E) where V is a finnite set and E is a set of two-element subsets
of V .
Adjacent
: Suppose G = (V; E) is a graph and (u,v) a member of V . Then, u is adjacent to v if uv is an edge in
G. This is denoted: u (tilda) v.
Degree
Let G = (V; E) be a graph and let v be a member of V . The degree of v is the number of edges with
which v is incident. We denote this: dG(v) or simply d(v) (when there is no confusion about the
graph in question).
Max/Min degree of G
The maximum degree of a vertex in G is denoted (triangle) (G). The
minimum degree of a vertex in G is denoted (small delta)(G).
regular graph
Regular graphs: If all vertices in G have the same degree, we call G regular
The sum of the degrees of the vertices of G
is twice the number of edges
Subgraph
Let G,H be graphs. H is a subgraph of G if V(H) is a subset of V(G) and E(H) is a subset of V(G)
Spanning subgraph
a sub graph with verts equal to those of the original graph
Induced Subgraph
, an induced subgraph (induced by a subset A of the vertices) includes the edges of
H with endpoints that are both vertices in A (and only those edges).
Clique
A subset of vertices is a clique provided any two distinct vertices in the subset are adjacent. The “clique number” of G is the size of the largest clique; it is denoted (weird w)(G)
independent sets
subset of vertices where no two vertices are adjacent. denoted alpha(G)
complement
the complement of G has the same vertices as G but has every edge that G does not
have (and no more).
A subset V (G) is a clique of G if and only if
it is an independent set of the complement of G
Let G be a graph with at least six vertices. Then
Then (weird w)(G)>= 3 or (weird w)(Gcompliment) >=3
Walk
let G={V,E} be a graph. A walk in G is a sequence of Verticies with each vertex adjacent to the next that is W=(vo,v1,….,vt) with all adjacent
Path
a path in a graph is a walk with no repeated verticies
Component
a component of G is a subgraph of G induced on an equivalence class of the is-connected-to relation on V(g)
connected
a graph is called connected provided each pair of vertices in the graph are connected by a path.
Cut Vertex/Cut Edge
cut vertex of G provided G-v has more compnenets than G. Cut edge off G provided G-e has more cmponents than G
If there is an (x,y)-walk in G
then there is an (x,y)-path in G
Let G be a graph, the is-connected to relation is
an equivalence relation on V(g)
Let G be a connected graph and suppose e in E(g) is a cut edge of G. Then
G-e has exactly two components`
Cycle
a cycle is a walk of at least three in which the first and last vertex are the same with no other repeated vertices. A cycle also refers to the graph or sub graph consisting of the vertices and edges of such a walk. A cycle on n vertices is denoted Cn.
Forest
Let G be a graph, if G contains no cycles, then G is acyclic. Alternatively, we call G a forest