[go: up one dir, main page]
Scribd
Upload
161 views4 pages

Discrete Math Proofs & Theorems

The document discusses solutions to discrete mathematics assignment problems. It includes: 1) A proof that the set of positive integers crossed with itself (Z+ × Z+) is countable by defining an injection from it to the positive integers. 2) A proof of the handshaking theorem and corollaries relating the number of edges and minimum/maximum degrees of vertices. 3) The maximum number of edges in a bipartite graph with 6 vertices is 9. 4) The degree sequence of a graph's complementary graph is the reverse of the original graph with each degree subtracted from n-1, where n is the number of vertices.

Uploaded by

Prujit Marni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
161 views4 pages

Discrete Math Proofs & Theorems

The document discusses solutions to discrete mathematics assignment problems. It includes: 1) A proof that the set of positive integers crossed with itself (Z+ × Z+) is countable by defining an injection from it to the positive integers. 2) A proof of the handshaking theorem and corollaries relating the number of edges and minimum/maximum degrees of vertices. 3) The maximum number of edges in a bipartite graph with 6 vertices is 9. 4) The degree sequence of a graph's complementary graph is the reverse of the original graph with each degree subtracted from n-1, where n is the number of vertices.

Uploaded by

Prujit Marni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Discrete Mathematics Assignment 4

November 2020

GROUP 17

1. Solution:

To prove: Z+ × Z+ is countable.

Let us define the function f as:

f : Z+ × Z+ → Z+ ,f( m,n) = ( m+n−1)2( m+n−2) +m

Let us first evaluate the formula for a few pairs;


( 1+1−1) ( 1+1−2)
f( 1,1) = 2 +1 = 20 +1 = 1
( 1+2−1) ( 1+2−2)
f( 1,2) = 2 +1 = 22 +1 = 2
( 2+1−1) ( 2+1−2)
f( 2,1) = 2 +2 = 22 +2 = 3
( 1+3−1) ( 1+3−2)
f( 1,3) = 2 +1 = 26 +1 = 4
( 2+2−1) ( 2+2−2)
f( 2,2) = 2 +2 = 26 +2 = 5
( 3+1−1) ( 3+1−2)
f( 3,1) = 2 +3 = 26 +3 = 6

We then note that f( m,n) represents the position of ( m,n) in the path with
( 1,1) in 1st position, ( 1,2) in 2nd position, ( 2,1) in 3rd position, etc.

f one-to-one
Let us assume that ( a,b) ∈ Z+ × Z+ and ( m,n) ∈ Z+ × Z+ such that a and
b have the same depiction.

f( a,b) = f( m,n)

1
By the definition of the function f, the image of f then represents the same
element in the path. However, each value is unique along the path and thus
the corresponding values need to be in the same location.

( a,b) = ( m,n)

We then note that f( a,b) = f( m,n) implies ( a,b) = ( m,n) for all
( a,b) ∈ Z+ × Z+ and for all ( m,n) ∈ Z+ × Z+ . By the definition of
one-to-one, f is then one-to-one.

f onto
Let c ∈ Z+ .
Let ( a,b) be the c ordered pair in the path.
By the definition of f:

f( a,b) = c
We then note that for every c ∈ Z+ ,there exists an element ( a,b) ∈ Z+ × Z+
such that f( a,b) = c. By the definition of onto, f is then onto.

Countable
We showed that f is onto and one-to-one, which implies that f is a one-to-one
correspondence between Z+ and Z+ × Z+ . This also means that Z+ × Z+
is countable as Z+ is countable.

4. Solution:

Handshaking theorem: An undirected graph with vertices V and m edges


has the property : X
2m = deg( v)
v=V

2e
( a) Prove: v ≥m

By the definition of handshaking theorem, the sum of the degrees is twice


the number of edges.
v
X
2e = deg( i)
i=1

We know that m is the minimum degree, thus the degree of each vertex is
larger than or equal to m.

2
v
X v
X
2e = deg( i) ≥ m = mv
i=1 i=1

We have then obtained the inequality 2e ≥ mv.


Divide each side of the inequality by v:
2e
v ≥m

2e
( b) Prove: v ≤m

By the definition of handshaking theorem, the sum of the degrees is twice


the number of edges.
v
X
2e = deg( i)
i=1

We know that M is the maximum degree, thus the degree of each vertex is
smaller than or equal to M.
v
X v
X
2e = deg( i) ≤ M = Mv
i=1 i=1

We have then obtained the inequality 2e ≤ M v.


Divide each side of the inequality by v:
2e
v ≤M

5. Solution:

Maximum number of edges in a bipartite graph on 6 vertices is 9.

Maximum number of edges in a bipartite graph on 6 vertices is 36.

v2
Maximum number of edges in a bipartite graph with v vertices = 4

3
6. Solution:

The degree sequence of a graph is the sequence of the degrees of the vertices
of the graph in non–increasing order.
The complementary graph G of a simple graph G has the same vertices of
G and two vertices are adjacent in G if and only if they are not adjacent in
G.
If G is a simple graph of n vertices, then
G ∪ G = Kn , the complete graph of n vertices.
The degree of every vertex of Kn is n-1.

Suppose G is a simple graph and is the degree sequence of G. then, because


G ∪ G = Kn and degree of every vertex Kn is n-1, the degree of a vertex in
G is ( n-1) -x, when every the degree of the vertex in G is x.
Hence, the degree sequence of G is
( n-1) - dn , ( n-1) - dn−1 ,............., ( n-1) - d2 , ( n-1) - d1

You might also like