  In this paper we explore the design of sequent calculi operating on graphs.
For this purpose, we introduce a set of logical connectives allowing us to
extend the correspondence between cographs and classical propositional formulas
to any graph. We then provide sequent calculi operating on these formulas, we
prove cut-elimination and that formula encoding the same graph are logically
equivalent. We show that these systems provide conservative extensions of
multiplicative linear logic (with and without mix) and classical propositional
logic. We conclude by showing that one of these systems is equivalent to the
graphical logic GS defined via a system of context-free graph rewiring rules,
therefore providing an alternative proof of analyticity for this logic over
graphs.
