Chapter 2 Flashcards
Number of edges in a complete K.n graph:
(p(p-1))/2 , where p is the order.
Thm: Sum of the vertex degrees in a graph is equal to twice the # of edges
Because each edge contributes 2 to the total vertex degree and 1 to the total edge count.
Thm: Every graph contains an even # of edd vertices
Split the graph into its odd and even vertices, set the total degree count equal to 2q (twice the edges). Find that since 2q even, and the summed even deg is even, the only way for the odd vertices to also be even is if there is an even number of them.
If a graph has order K>=2, it is impossible that all vertices have different degree.
BWOC, assume all vertices have diff degree. Order vertices s.t. deg(v.j) = j-1 where j = 1,2,…,p (p=order max degree is p-1).
Observe v.k adjacent to all vertices, in particular v.1. But, the deg(v.1) - 0, Thus contradiction.
If every vertex of a graph G has degree r:
we say G is regular graph of degree r, or G is r-regular
What can be said about r-regular bipartite graph?
Number of edges is r|X.bar| = r|Y.bar|, thus |X.bar| = |Y.bar|
We say graphs G.1, G.2 are isomorphic if:
there exists a bijection phi: V(G.1) -> V(G.2) s.t u,v in V(G.1) are adjacent IFF phi(u), phi(v) are adjacent in G.2. We say G.1 ~ G.2.
Thm: Isomorphism is an equivalence relation.
Reflexivity: Let phi(v) = v. This is a bijection from V(G) to V(G), which preserves adjacency.
Symmetry: Suppose G.1 ~ G.2, let phi: V(G.1) -> V(G.2) be the adjacency preserving isomorphism. Then phi^-1: V(G.2) -> V(G.1) is an isomorphism.
Transitivity: Let phi: V(G.1) -> V(G.2), T: V(G.2) -> V(G.3) both be isomorphic. Then T of phi is an isomorphism
Thm: If G.1~G.2, and phi is the isomorph, degv in G.1 is equal to degphi(v) in G.2.
Let v be adjacent to only {N.1,N.2,…,N.k} s.t. degv=k.
Then phi(v) is adjacent to only {phi(N.1),phi(N.2),…,phi(N.k)} so,
Thus degphi(v) = k.
Correlary: If G.1~G.2, they have same list of vertex degrees.
H is a subgraph of another graph G if:
H is a subgraph of G if: V(H) is subset of V(G), and E(H) is subset of E(G).
Def/ V’ is subset of V(G). V’ induces:
V induces a subgraph G; s.t. V(G’) = V’ and E(G’) is the largest possible subset of E(G)
Def/ Let E; is subset of E(G). E’ induces a
E’ induces a subgraph G’, s.t. E(G’) = E’ and all v in V(G’) are endpoints of edges in E’.
Thm: Let G be a graph w/ E(G) != empty set. If all vertex induces subgraphs are regular, G is complete.
There exists an edge v.1.v.2. Let u be any other vertex. The subgraph induced by {v.1, v.2, u} is regular (by hypoth.), so is isomorphic to K.3
Thus, u is adjacent to v.1, v.2. and v.1 is thus adjacent to all vertices since u arbitrary.
To show that u adjacent to all vertices, we use same argument b/c we now know uv.1 in E(G), thus u connected to all other vertices.
Since u arbitrary, done.
Def/ a u-v walk is:
a sequence of adjacent edges, where the first is incident to u, and the last in incident to v. Can revisit edges or vertices.D
Def/ A u-v trail is:
A walk that does not repeat edges, but can repeat vertices.
Def/ A u-v path is:
A walk that does not repeat edges or vertices.
Def/ u, v in V are connected if:
There exists a u-v path.
Def/ A graph is connected if:
A graph is connected if: for every pair of vertices (u,v), then u, v are connected.
A connected component H is:
A subgraph of G, s.t. H is not a proper subgraph of a connected subgraph. i.e it is a connected component, but defined as the biggest subgraph of that connected component.
Thm/ Every u-v trail (or walk) contains a u-v path.
Let u.1,u.2,…u.n,v be the u-v trail.
Suppose (u.k, u.j) with k < j is the first pair of repeated vertices. Create a new trailed u,u.1,u.2,….u.k,u.j+1,…,u.n, v.
Repeat until there are no duplicate vertices.
Thm: If G is connected but not complete, there exists a triple {u,v,w} s.t. only uv, vw are edges AKA there exists an incomplete subgraph.
There exists u.0 and w which are not adjacent because it is not complete.
Let u.0, u.1, …, u.2, w be the shortest path from u.0 to w.
Now we claim that u.n-1 and w are not adjacent. If they are, then there exists a shorter path from u.0 to w. Thus, {u.n-1, u.n, w} is the desired triple.
Def: A u-v circuit:
If u-v is a trail w/ 3+ vertices and u=v, u-v forms a circuit. Fine to repeat vertices, but CANNOT repeat edges.
Def/ A u-v cycle is:
A u-v cycle is a circuit with no repeated vertices. AKA p>=3, u = v, and no repeated edges or vertices.
Thm: If del = min(deg(v), v in V) >= 2, G has a cycle. (has to have 3 vertices to be circuit by def)
Pick any vertex v.0. By min degv, v.0 adjacent to v.n, v.1, s.t v.1 != v.n.
Then, choose v.1 and repeat argument. You will find that it has another neighbor that isn’t v.0. If it is one that has already been visited, there is your cycle.
Keep repeating until v.n-1 is adjacent to v.n AKA you hit a vertex you have already visited.
Def/ If e is an edge, G-e is:
G-e is a subgraph with same edges and vertices as G, except for e (e is missing)
If v is a vertex, G-v is:
G-v is a subgraph induced by the vertex set V(G)-v.
Def/ An edge e in E(G) is a bridge if:
e is a bridge if G is connected but G-e is not.
Def/ A vertex v is a (1) cut-vertex if:
It is a (1) cut vertex is the graph G is connected but G-v is not.
Thm/ An edge e is a bridge IFF it is not on a cycle.
Pf (<=). If not on a cycle => e is a bridge. BWOC, suppose e not on a cycle and is not a bridge. Then, G-e is connected, so if e = uv, there exists a uv path in G-e.
This path P, together with removed edge e forms a cycle in G. Thus, contradiction.
(=>) e is a bridge => it is not a cycle. BWOC, assume e is a bridge, but e is on a cycle.
Let u,v be any 2 vertices in V(G). There exists a path P from u to v. If P does not contain e, then u, v connected in G-e thus e not a bridge thus contradiction.
If e in path P, can form a new path from u.1 to v which doesn’t contain e, b/c cycle. Then u,v connected in G-e, G-e connected b/c uv arbitrary. Thus, e is not a bridge
Thm: If G is order p >= 3 and connected, and e is a bridge, then e is incident to a cut-vertex.
By def, G-e is not connected.
Let e = uv, since G has order 3 or more, there exists vertex u.1 adjacent to u. Thus, u.1 adj to u, u adj to v with edge e.
Claim: There is only one u.1 - v path. If not, a cycle is made by this path and edges u.1u and uv. And bridge cannot be on cycle.
Then G-u is not connected since there is no u.1-v path in G-u. Thus, u is a cut vertex.
Def/ A k-vertex cut is:
A k-vertex cut is a set V’ subset of G(V) of size k, s.t. G-V’ is not connected.
What is special about K.n and vertex cuts?
K.n has no vertex cuts, b/c/ removing vertices just results in another complete graph.
Def/ The vertex connectivity Kap(G) is:
Vertex connectivity is the minimum K for which G has a K-vertex cut
Def/ G is k-connected if:
K <= Kap(G). So anything connected is 1 connected. So, Kap(G) = 4, then it is 1,2,3,4 connected.
Def/ A k-edge cut is:
A k-edge cut is a set E’ subset of E(G) s.t. G-E’ is not connected
Def/ The edge-connectivity Kap’(G) is:
Kap’(G) is the minimum K s.t. G has a k-edge cut.
Thm: Kap <= Kap’ <= min. vertex degree
Let v be vertex w/ smallest degree del. There is a del-degree edge cut given by the set of edges incident to v.
Base case: If Kap’ = 0, G not connected, Kap = Kap’ = 0. Induct of Kap’, suppose Kap(G) <= Kap’(G) for all graphs where Kap’(G) = n-1
Let G be graph with Kap’(G) = n. Let e be an edge e in an n-edge cut of G. Then, E’ = {e} is a n-1 edge cut of G-e = H.
Then, Kap’(H) = n-1, so Kap(H) <= n-1.
There exists a vertex cut S of H w/ n-1 elements.
Case 1: G-S is not connected. Then Kap(G) = Kap(H) <=n-1 = Kap’(G).
Case 2: G-S is connected, then e is a bridge of G-s, since G-S-e = H-S, which is not connected.
a. Case order of G-S is 2: Then Kap(G) <= V(G) -1 = Kap(H)+2-1 = n-1
b. Case order G-S >= 3. G-S has a cut vertex v, thus S union {v} is a vertex cut of G, and Kap(G) <= Kap(H)+1 <= n.
