Chapter 2

Question 1

Number of edges in a complete K.n graph:

Answer 1

(p(p-1))/2 , where p is the order.

Question 1

Thm: Sum of the vertex degrees in a graph is equal to twice the # of edges

Answer 1

Because each edge contributes 2 to the total vertex degree and 1 to the total edge count.

Question 2

Thm: Every graph contains an even # of edd vertices

Answer 2

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.

Question 3

If a graph has order K>=2, it is impossible that all vertices have different degree.

Answer 3

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.

Question 4

If every vertex of a graph G has degree r:

Answer 4

we say G is regular graph of degree r, or G is r-regular

Question 5

What can be said about r-regular bipartite graph?

Answer 5

Number of edges is r|X.bar| = r|Y.bar|, thus |X.bar| = |Y.bar|

Question 6

We say graphs G.1, G.2 are isomorphic if:

Answer 6

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.

Question 7

Thm: Isomorphism is an equivalence relation.

Answer 7

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

Question 8

Thm: If G.1~G.2, and phi is the isomorph, degv in G.1 is equal to degphi(v) in G.2.

Answer 8

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.

Question 9

H is a subgraph of another graph G if:

Answer 9

H is a subgraph of G if: V(H) is subset of V(G), and E(H) is subset of E(G).

Question 10

Def/ V’ is subset of V(G). V’ induces:

Answer 10

V induces a subgraph G; s.t. V(G’) = V’ and E(G’) is the largest possible subset of E(G)

Question 11

Def/ Let E; is subset of E(G). E’ induces a

Answer 11

E’ induces a subgraph G’, s.t. E(G’) = E’ and all v in V(G’) are endpoints of edges in E’.

Question 12

Thm: Let G be a graph w/ E(G) != empty set. If all vertex induces subgraphs are regular, G is complete.

Answer 12

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.

Question 13

Def/ a u-v walk is:

Answer 13

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

Question 14

Def/ A u-v trail is:

Answer 14

A walk that does not repeat edges, but can repeat vertices.

Question 15

Def/ A u-v path is:

Answer 15

A walk that does not repeat edges or vertices.

Question 16

Def/ u, v in V are connected if:

Answer 16

There exists a u-v path.

Question 17

Def/ A graph is connected if:

Answer 17

A graph is connected if: for every pair of vertices (u,v), then u, v are connected.

Question 18

A connected component H is:

Answer 18

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.

Question 19

Thm/ Every u-v trail (or walk) contains a u-v path.

Answer 19

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.

Question 20

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.

Answer 20

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.

Question 21

Def: A u-v circuit:

Answer 21

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.

Question 22

Def/ A u-v cycle is:

Answer 22

A u-v cycle is a circuit with no repeated vertices. AKA p>=3, u = v, and no repeated edges or vertices.

Question 23

Thm: If del = min(deg(v), v in V) >= 2, G has a cycle. (has to have 3 vertices to be circuit by def)

Answer 23

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.

Question 24

Def/ If e is an edge, G-e is:

Answer 24

G-e is a subgraph with same edges and vertices as G, except for e (e is missing)

Question 25

If v is a vertex, G-v is:

Answer 25

G-v is a subgraph induced by the vertex set V(G)-v.

Question 26

Def/ An edge e in E(G) is a bridge if:

Answer 26

e is a bridge if G is connected but G-e is not.

Question 27

Def/ A vertex v is a (1) cut-vertex if:

Answer 27

It is a (1) cut vertex is the graph G is connected but G-v is not.

Question 28

Thm/ An edge e is a bridge IFF it is not on a cycle.

Answer 28

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

Question 29

Thm: If G is order p >= 3 and connected, and e is a bridge, then e is incident to a cut-vertex.

Answer 29

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.

Question 30

Def/ A k-vertex cut is:

Answer 30

A k-vertex cut is a set V’ subset of G(V) of size k, s.t. G-V’ is not connected.

Question 31

What is special about K.n and vertex cuts?

Answer 31

K.n has no vertex cuts, b/c/ removing vertices just results in another complete graph.

Question 32

Def/ The vertex connectivity Kap(G) is:

Answer 32

Vertex connectivity is the minimum K for which G has a K-vertex cut

Question 33

Def/ G is k-connected if:

Answer 33

K <= Kap(G). So anything connected is 1 connected. So, Kap(G) = 4, then it is 1,2,3,4 connected.

Question 34

Def/ A k-edge cut is:

Answer 34

A k-edge cut is a set E’ subset of E(G) s.t. G-E’ is not connected

Question 35

Def/ The edge-connectivity Kap’(G) is:

Answer 35

Kap’(G) is the minimum K s.t. G has a k-edge cut.

Question 36

Thm: Kap <= Kap’ <= min. vertex degree

Answer 36

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.