Problem $1(20$ points$).$ Let $I=(G=(V,A),(l_a{)}_{\text{a}\text{i}\text{n}\text{A}},(s,t),r)$ be a selfish rout$-$

ing instance with a single commodity and affine latency functions. Given an arbi$-$

trary subgraph $H=(V,A_H)$ of $G,$ define $I_H$ as the instance that we obtain from $I$

by restricting to the subgraph $H,$ i$.$e$.,I_H=(H=(V,A_H),(l_a{)}_{ain{A}_H}(s,t),r).$ Let

$d(H)=c(f_H)$ denote the common latency of all flow$-$carrying paths under a Nash

flow $f_H$ of $I_H$; we define $d(H)=$ if $s$ and $t$ are disconnected in $H.$

$($a$)$ Show that for every subgragph $H$ of $G$ : $d(G)\frac{4}{3}d(H).$

$($b$)$ Give an example that shows that the bound in $($a$)$ is tight.