hw2 Soln PDF

MATH 428Fall, 2016
Assignment #2 Solutions
35 points
1. (5 points) Recall that the Petersen graph P is defined by
V (P ) = { all pair of elements from {1, ..., 5}},
and
E(P ) = {ST |S, T V (P ) and S T = }.
Prove that K3 , the complete graph on three vertices, is not a subgraph of the Petersen graph.
[Hint: Use the definition of the Petersen graph, instead of looking at the drawing of the graph]
Ans. Assume for contradiction that P has a K3 as a subgraph on vertices S1 , S2 and S3 are three
vertices of P . Thus, S1 S2 = S1 S3 = S2 S3 = . Since, each of the vertices is of
cardinality two, this implies that |S1 S2 S3 | = 6 > 5 = |{1, 2, . . . , 5}| a contradiction with
the fact that S1 , S2 , S3 were subsets of {1, ..., 5}.
2. (5 points) [Book 1.15] Draw all connected graphs of order 5 in which the distance between
every two distinct vertices is odd. Explain why you know that you have drawn all such graphs.
Ans. Since the graph is connected it must have dist(u, v) < for all pairs of vertices u and v.
We claim that the only such graph on 5 vertices is the complete graph K5 . We prove this
by showing that in a graph where the distance between vertices is odd, the distance between
every two vertices must be in fact 1, or equivalently every pair of vertices are connected with
an edge. Assume for contradiction that this is not the case. Then there must be a graph
G satisfying the above conditions and yet having vertices u and v with dist(u, v) > 1. This
means that d := dist(u, v) 3 since 2 is an even number. Let (u = u0 , u1 , u2 , ..., ud = v) be a
shortest uv-path. Note that dist(u, ud1 ) = d 1 since (i) (u0 , u1 , ..., ud1 ) is a uud1 -path of
length d 1, and (ii) if there was a shorter uud1 path, this would lead to a shorter uv path
contradicting that d = dist(u, v). Hence, dist(u, ud1 ) = d 1 an even number, contradicting
our assumption that G had only odd vertex distances.
3. (5 points) [Book 1.22] Let G be a disconnected graph. By Theorem 1.11 (also proved in
class), G is connected. Prove that diam(G) 2. [We hinted to this in class]
Ans. Suppose that G is disconnected. Let u, v be two vertices of G. We break to two cases:
Case 1. uv 6 E(G): In this case, uv E(G).

Case 2. uv E(G). In this case u and v are in the same connected component of G, and since
G is disconnected, there must be a vertex w in a different connected component than
the one with u and v. We have uw, vw 6 E(G) and hence uw, vw E(G).
In Case 1. distG (u, v) = 1 and in Case 2. distG (u, v) = 2. Hence, diam(G) 2.
4. (5 points) [Book 1.25] Let G be a graph of order 5 or more. Prove that at most one of G
and G is bipartite.
Ans. Let V1 , V2 be a bipartition of the vertices of G. Namely,
V1 V2 = V (G)
1
V1 V2 =
G has no edges with both endpoints in V1 or both endpoints in V2 .
Note that since |V (G)| 5 it must be that |V1 | > 3 or |V2 | > 3. However, in both cases G
contains a K3 (a triangle) and hence is not a bipartite graph. This shows that if G is bipartite
then G cannot be bipartite. The proof of the other direction is identical, as G = G.
5. (5 points) [Book 2.20] Show that if G is a connected graph that is not regular, then G
contains adjacent vertices u and v such that deg(u) 6= deg(v).
Ans. We prove the contrapositive. Assume that G is a connected graph for which all adjacent
vertices have the same degree. Since G is connected, for every pair of vertices u and v, there
is a uv-path in G. Going through the edges of a uv path (u = u0 , u1 , . . . , ut = v), we have
deg(u) = deg(u1 ) = = deg(v). This implies that G must be a regular graph as for every
u, v V (G) we have deg(u) = deg(v).
6. (5 points) What is the maximum size of a bipartite graph of order n?
Ans. The maximum size of a bipartite graph is bn/2cdn/2e. Any bipartite graph can be partitioned
into two parts, such that only allowed edges are going from one part to another. So, if the
first part has k vertices and the second part has n k vertices, maximum number of allowed
edges is k (n k). We claim that this number is maximized when k = bn/2c. Assume
without loss of generality that k bn/2c, so k = bn/2c ` where ` 0. And the maximum
number of edges when the parts are of size k and n k is
(bn/2c `)(dn/2e + `) = bn/2c dn/2e ` (` (dn/2e bn/2c)).
Note that if k < bn/2c then ` 1 and thus ` (dn/2e bn/2c is positive, and as a result
(bn/2c `)(dn/2e + `) < bn/2c dn/2e.
This maximum is achieved by the complete bipartite graph Kbn/2c,dn/2e .
7. (5 points) Prove that if G is a graph with n vertices and m > n1

2 edges, then G must be
n1

connected. [ 2 is the binomial coefficient. Read about it here!]
Ans. Note that if the graph has a vertex of degree n 1 then it must be connected. If the graph
has a vertex v of degree n 2, let v1 , ..., vn2 be the neighbors of v, and u be the nonneighbor
of v. The maximum number of edges with both endpoints in {v1 , ..., vn2 } {v} is n1

2 ,
thus u must have an edge to at least a vertex from {v1 , ..., vn2 } making G connected. Thus
the only case left is when (G) n 3. In this case the graph has at most n(n 3)/2 edges.
However,
n2 3n + 2 n2 3n

n1 (n 1)(n 2) n(n 3)
= = > = .
2 2 2 2 2
Hence this case is not possible for G, as it would mean G does not have more than n1

2
edges.

hw2 Soln PDF

Uploaded by

Copyright:

Available Formats

hw2 Soln PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

hw2 Soln PDF

Uploaded by

Copyright:

Available Formats

MATH 428Fall, 2016

1. (5 points) Recall that the Petersen graph P is defined by

V (P ) = { all pair of elements from {1, ..., 5}},

Case 1. uv 6 E(G): In this case, uv E(G).

In Case 1. distG (u, v) = 1 and in Case 2. distG (u, v) = 2. Hence, diam(G) 2.

Ans. Let V1 , V2 be a bipartition of the vertices of G. Namely,

6. (5 points) What is the maximum size of a bipartite graph of order n?

(bn/2c `)(dn/2e + `) = bn/2c dn/2e ` (` (dn/2e bn/2c)).

(bn/2c `)(dn/2e + `) < bn/2c dn/2e.

This maximum is achieved by the complete bipartite graph Kbn/2c,dn/2e .

7. (5 points) Prove that if G is a graph with n vertices and m > n1

You might also like