Let $B$ be the set of isomorphism classes of finite graphs. Let $V$ be the $k$-vector space freely generated by $B$. I have heard that $V$ carries the structure of a Hopf algebra, and would like to understand the details.
The multiplication is defined by linear extension of the disjoint union of graphs. The unit is the empty graph. The comultiplication sends a graph $G$ to the sum $\sum_{S \subseteq V(G)} G|_S \otimes G|_{V(G) \setminus S}$, running over all subsets of vertices of $G$. The counit maps the empty graph to $1$, and all other graphs to $0$. I have checked that we get a commutative cocommutative bialgebra.
Question. How to define the antipode?
Although the antipode $S$ of a Hopf algebra is unique, I cannot come up with it. I am pretty sure that the antipode maps a graph to an alternating sum of graphs. Only then $V \to V \otimes V \xrightarrow{S \otimes V} V \otimes V \to V$ can cancel to $V \to k \to V$.
For the incidence Hopf algebras arising out of graphs the author in the article http://www.dmtcs.org/pdfpapers/dmAO0146.pdf gives a formula. For general incidence Hopf algebras one can look at http://home.gwu.edu/~wschmitt/papers/iha.pdf for the antipode formula.