diff --git a/requirements-swh-graph.txt b/requirements-swh-graph.txt
new file mode 100644
--- /dev/null
+++ b/requirements-swh-graph.txt
@@ -0,0 +1 @@
+swh.graph >= v0.3.2
diff --git a/requirements-swh.txt b/requirements-swh.txt
--- a/requirements-swh.txt
+++ b/requirements-swh.txt
@@ -1,5 +1,4 @@
 swh.core[db,http] >= 0.14.0
-swh.graph >= v0.3.2
 swh.model >= 0.3
 swh.objstorage >= 0.0.17
 swh.scheduler >= 0.7.0
diff --git a/setup.py b/setup.py
--- a/setup.py
+++ b/setup.py
@@ -48,7 +48,10 @@
     install_requires=parse_requirements() + parse_requirements("swh"),
     setup_requires=["setuptools-scm"],
     use_scm_version=True,
-    extras_require={"testing": parse_requirements("test")},
+    extras_require={
+        "testing": parse_requirements("test"),
+        "graph": parse_requirements("swh-graph"),
+    },
     include_package_data=True,
     zip_safe=False,
     entry_points="""
diff --git a/swh/vault/cli.py b/swh/vault/cli.py
--- a/swh/vault/cli.py
+++ b/swh/vault/cli.py
@@ -70,7 +70,6 @@
     and outputs it to the given file.
     """
     from swh.core import config
-    from swh.graph.client import RemoteGraphClient
     from swh.objstorage.factory import get_objstorage
     from swh.storage import get_storage
 
@@ -101,10 +100,21 @@
                 f"an explicit --cooker-type."
             )
 
+    try:
+        from swh.graph.client import RemoteGraphClient  # optional dependency
+
+        graph = RemoteGraphClient(**conf["graph"]) if conf.get("graph") else None
+    except ModuleNotFoundError:
+        if conf.get("graph"):
+            raise EnvironmentError(
+                "Graph configuration required but module is not installed."
+            )
+        else:
+            graph = None
+
     backend = InMemoryVaultBackend()
     storage = get_storage(**conf["storage"])
     objstorage = get_objstorage(**conf["objstorage"]) if "objstorage" in conf else None
-    graph = RemoteGraphClient(**conf["graph"]) if "graph" in conf else None
     cooker_cls = get_cooker_cls(cooker_name)
     cooker = cooker_cls(
         obj_type=cooker_name,
diff --git a/swh/vault/cookers/__init__.py b/swh/vault/cookers/__init__.py
--- a/swh/vault/cookers/__init__.py
+++ b/swh/vault/cookers/__init__.py
@@ -1,4 +1,4 @@
-# Copyright (C) 2017-2020  The Software Heritage developers
+# Copyright (C) 2017-2021  The Software Heritage developers
 # See the AUTHORS file at the top-level directory of this distribution
 # License: GNU General Public License version 3, or any later version
 # See top-level LICENSE file for more information
@@ -10,7 +10,6 @@
 
 from swh.core.config import load_named_config
 from swh.core.config import read as read_config
-from swh.graph.client import RemoteGraphClient
 from swh.storage import get_storage
 from swh.vault import get_vault
 from swh.vault.cookers.base import DEFAULT_CONFIG, DEFAULT_CONFIG_PATH
@@ -90,7 +89,18 @@
 
     storage = get_storage(**vcfg.pop("storage"))
     backend = get_vault(**vcfg)
-    graph = RemoteGraphClient(**vcfg["graph"]) if "graph" in vcfg else None
+
+    try:
+        from swh.graph.client import RemoteGraphClient  # optional dependency
+
+        graph = RemoteGraphClient(**vcfg["graph"]) if vcfg.get("graph") else None
+    except ModuleNotFoundError:
+        if vcfg.get("graph"):
+            raise EnvironmentError(
+                "Graph configuration required but module is not installed."
+            )
+        else:
+            graph = None
 
     return cooker_cls(
         obj_type,
diff --git a/tox.ini b/tox.ini
--- a/tox.ini
+++ b/tox.ini
@@ -4,6 +4,7 @@
 [testenv]
 extras =
   testing
+  graph
 deps =
   pytest-cov
 commands =
@@ -28,6 +29,7 @@
 [testenv:mypy]
 extras =
   testing
+  graph
 deps =
   mypy
 commands =
@@ -41,6 +43,7 @@
 usedevelop = true
 extras =
   testing
+  graph
 deps =
   # fetch and install swh-docs in develop mode
   -e git+https://forge.softwareheritage.org/source/swh-docs#egg=swh.docs
@@ -60,6 +63,7 @@
 usedevelop = true
 extras =
   testing
+  graph
 deps =
   # install swh-docs in develop mode
   -e ../swh-docs