Solutions To MAT310 Assignment[Discrete Mathematics]

MAT310 Assignment

Photo Credit: tue.nl

(1)  Show that every vertex of $G$ belongs to exactly one component of $G$. Hence show that every edge of $G$ belongs to exactly one component of $G$.

(2)  Prove that if a graph $G$ contains a $u-v$ walk of length $L$, then $G$ contains a $u-v$ path of length at most $L$.

(3)  Let $F$ be a finite field containing a subfield $k$ with $q$ elements where $m=[f::k]$, then show that $f$ has $q^m$ elements.

(4)  Show that for every finite field $\mathbb{F}_q$ and every positive integer $n$, there exists an irreducible polynomial in $\mathbb{F}_q[x]$ of degree $n$.

                                                                            Solutions: 

(1) I solved this question under MAT310 Test solutions,  click here to see solution. 

but i will share the solution again.

To show this, we need to define a component graph, A graph $G$ is a component graph $c(G)$  if $H\subset{G}$ i.e $H$ is a subgraph of $G$.

Then $H$ is said to be a component of $G$ if:

(i) $H$ is connected

(ii) $H$ is not contained in any connected subgraph of $G$ which has more vertices or edges than $H$.

In the graph below it is evident that $H$ is a connected component of $G$ and for every vertex $v_1\in{G}$ there exists a $u_1\in{H}$ and for every edge $e_1\in{G}$ there exists a $b_1\in{H}$, and hence the number of connected component is $2$.

A connected component graph

(2)  Proof:  Let $W$  be a $u–v$ walk in $G$. We prove this theorem by induction on the length of $W$. If $W$ is of length $1$ or $2$, then it is easy to see that $W$ must be a path.
For the induction hypothesis, suppose the result is true for all walks of length less than k, and suppose $W$ has length $k$. Say that $W$ is

                                                         $u=w_0,w_1,w_2,...,w_{k-1},w_k=v$

where the vertices are not necessarily distinct. If the vertices are in fact distinct, then $W$ itself is the desired $u–v$ path. If not, then let $j$ be the smallest integer such that $w_j = w_r$ for some $r > j$. Let $W_1$ be the walk

                                             $u=w_0,...,w_j,w_{r+1}=v$

This walk has length strictly less than $k$, and therefore the induction hypothesis implies that $W_1$ contains a $u–v$ path. This means that $W$ contains a $u–v$ path, and the proof is complete.

(3)  Proof: Let F be a vector space over K, and finite-dimensional since F is finite. Denote this dimension by m, then F has a basis over K consisting of m elements, say $b_1,. . . ,b_m$. Every element of F can be uniquely represented in the form $k_1b_1+k_mb_m$ where $k_1, . . . , k_m\in{K}$. Since each $k_i\in{K}$ can take q values, F must have exactly $q^m$ elements.

(4)  Refer back to my lecture on irreducible polynomials or propositions on polynomials.