left and right adjoint for inclusion functor

Question

A weighted graph G= consist of two set Vertex and Edge with functions $s$ (send edge to source from Edge to Vertex), $t$ (send edge to target from Edge to Vertex), root $r$ and weight function $w:E \rightarrow \mathbb{N}$.

G is finite if $V$ and $E$ is finite. A weighted tree is the same as above just take tree instead of graph. A weighted morphism between $G$ and $G'$ is morphism $\sigma$, where $\sigma_{V}$ is morphism between vertexs and $\sigma_{E}$ is morphism between Edges (so it is just normal graph morphism). One important thing is that in any category If we have homomorphism $\sigma$ between two objects G and G' then we have w(e) <= w($\sigma$(e)) so homomorphism does not decrease the weights.

With above definitions we have categories $Wgraph$ (category of weighted graphs), $FWgraph$ (category of weighted graphs with finite node and finite edge set) and $Wtree$ (category of weighted trees), $FWtree$ (category of weighted trees with finite node and finite edge set).

Question: Do inclusions

$i_1:$ $ Wtree \rightarrow Wgraph $ , $i_2:$ $ FWtree \rightarrow FWgraph $ have left or right adjoint?

I think about spanning tree and try to see it as functor which can be right adjoint but I am not sure. Should I show existence or anybody has direct functor for left or right adjoint ?

Answer 1

A formalization

You've now given a description of the category. Let me formalize it, so that we are all clear on what's going on.

A weighted (directed, based on the description you've given) graph $G$ consists of the data $(V,E,s,t,r,w)$, with $V, E$ sets and $s,t:E\to V$ arbitrary functions, $r:*\to V$ a fixed vertex, and $w:E\to \Bbb{N}$ a weight function. A morphism $G\to G'$ consists of a pair of maps $f:V\to V'$ and $g:E\to E'$ such that $s'g=fs$, $t'g=ft$, $r'=fr$, and $w'(g(e))\ge w(e)$ for all $e\in E$.

Since these graphs are directed, it's not quite clear what a tree should be, but I'll assume that it means there is a unique path from the root to any other vertex in the graph.

Since we have a root, it's much more likely that coproducts are preserved, since now coproduct is take the disjoint union of the graphs and then identify the vertices. And in fact, we can construct a right adjoint to the inclusion functor, treeification, which I'll write as $T$. This is essentially the construction of the universal cover.

The right adjoint

Let $G$ be a weighted graph. The vertex set of $TG$ is the set of all paths in $G$, i.e. $$V(TG)=\{ \text{finite sequences } e_0e_1e_2\cdots e_n, \text{ with $e_i\in E$, and $t(e_{i-1})=s(e_i)$ for $1\le i\le n$ and $s(e_0)=r$.}\} $$ The edges are pairs $(p,e)\in V(TG)\times E(G)$ with $pe$ also in $V(TG)$. Then $s(p,e)=p$, $t(p,e)=pe$, $r$ is the empty path, and we just need to define the weight function.

Note that we have a canonical map $TG\to G$ given on vertices by $e_0\cdots e_n\mapsto t(e_n)$ and on edges by $(p,e)\mapsto e$. Moreover there is a unique path from the root $r$ in $TG$ to any vertex $p$. It's essentially $p$ again. Let $p=e_0\cdots e_n$, and let $p_i = e_0\cdots e_i$. Then the unique path is $$(r,e_0)(p_0,e_1)(p_1,e_2)\cdots (p_{n-1},e_n).$$ Therefore $TG$ is in fact a tree.

First let's verify that on the level of unweighted graphs this gives a right adjoint.

Suppose I have a morphism $(f,g)$ from a tree $X$ to a graph $G$, then for all vertices $v\in V(X)$, there is a unique path $p_v$ from the root to $v$, and by definition, $f(p_v)$ is also a path in $G$, and thus a vertex in $TG$. So we define $f':V(X)\to V(TG)$ by $v\mapsto f(p_v)$. The action on the edges is then forced by $g'(e) = (f'(s(e)),g(e))\in E(TG)$. This gives a map of graphs $X\to TG$.

Conversely, if we have a map from $X$ to $TG$, then just compose with the canonical projection $TG\to G$ to get a map $X\to G$.

I'll leave it to you to check that these are inverse operations.

Now let's deal with the weightings. Let's just do the obvious thing and define $w(p,e)=w(e)$. Then $TG\to G$ stays a morphism of weighted graphs, and since the morphism conjugate to $X\to G$ was defined on edges by $g'(e)=(f'(s(e)),g(e))$, we have $w_{TG}(g'(e))=w_G(g(e))\ge w_X(e)$, so the conjugate remains a homomorphism of weighted graphs.

Thus $TG$ with this weighting gives a right adjoint to the inclusion of weighted trees into weighted graphs.

Note that $TG$ is usually not finite even if $G$ is, since if you have an accessible loop in the graph, we'll have infinitely many paths given by going round and round the loop.

Left Adjoint?

I'm not sure about a left adjoint. It seems like it doesn't exist. Here's my reasoning:

Most of the time, it seems like morphisms from a graph to a tree are empty. If you have a morphism from a graph to some tree, it forces all paths from the root to any fixed vertex to have the same length. But no tree has the property that all hom sets from it to any other tree are empty, since maps from a tree to itself always contains the identity. Thus a left adjoint can't exist.

Answer 2

Without a very precise description of the categories at hand it is, of course, impossible to answer. In any case, it seems unlikely that a left or right adjoint would exist. Firstly, what might the left/right adjoint on a graph with $n$ nodes and no vertices be? It would somehow need to produce out of thin air a tree on some number of nodes. It seems unlikely that there are such canonical trees. Second, if the inclusion has a right adjoint that it preserves coproducts. That seems unlikely since coproducts of graphs are probably their disjoint union. Coproducts of trees need to somehow stay connected, so if they exist at all they won't be preserves. So, this would imply the tree categories don't have coproducts. Coproducts are often how right adjoints are constructed, so it makes the existence of an adjoint less likely. Worse still, the same arguments holds for colimits. Some pushouts of trees are likely to still be trees. Would these then be preserved? Some careful definitions are required to further answer this question. Interesting question though.