diff --git a/docs/api.rst b/docs/api.rst
--- a/docs/api.rst
+++ b/docs/api.rst
@@ -48,6 +48,46 @@
 - ``"*:rel"`` node types allowing all edges to releases.
 
 
+Node & edge existence
+---------------------
+
+.. http:get:: /graph/node/:src
+
+    Check whether a given node exists in the graph or not.
+
+    :param string src: source node specified as a SWH PID
+
+    :statuscode 200: success
+    :statuscode 400: invalid PID
+    :statuscode 404: node not found
+
+    .. sourcecode:: http
+
+        HTTP/1.1 200 OK
+        Content-Type: text/plain
+
+        swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35
+
+
+.. http:get:: /graph/edge/:src/:dst
+
+    Check whether a given edge exists in the graph or not.
+
+    :param string src: source node specified as a SWH PID
+    :param string dst: destination node specified as a SWH PID
+
+    :statuscode 200: success
+    :statuscode 400: invalid PID(s)
+    :statuscode 404: node(s) not found
+
+    .. sourcecode:: http
+
+        HTTP/1.1 200 OK
+        Content-Type: text/plain
+
+        swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35 swh:1:dir:b5d2aa0746b70300ebbca82a8132af386cc5986d
+
+
 Leaves
 ------
 
@@ -118,15 +158,15 @@
 
        :param string src: starting node specified as a SWH PID
        :param string dst: destination node, either as a node PID or a node type.
-	   The traversal will stop at the first node encountered matching the
-	   desired destination.
+           The traversal will stop at the first node encountered matching the
+           desired destination.
 
        :query string edges: edges types the traversal can follow; default to
-	   ``"*"``
+           ``"*"``
        :query string traversal: traversal algorithm; can be either ``dfs`` or
-	   ``bfs``, default to ``dfs``
+           ``bfs``, default to ``dfs``
        :query string direction: direction in which graph edges will be followed;
-	   can be either ``forward`` or ``backward``, default to ``forward``
+           can be either ``forward`` or ``backward``, default to ``forward``
 
        :statuscode 200: success
        :statuscode 400: invalid query string provided
@@ -134,15 +174,15 @@
 
        .. sourcecode:: http
 
-	   HTTP/1.1 200 OK
-	   Content-Type: text/plain
-	   Transfer-Encoding: chunked
+           HTTP/1.1 200 OK
+           Content-Type: text/plain
+           Transfer-Encoding: chunked
 
-	   swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35
-	   swh:1:rev:52c90f2d32bfa7d6eccd66a56c44ace1f78fbadd
-	   swh:1:rev:cea92e843e40452c08ba313abc39f59efbb4c29c
-	   swh:1:rev:8d517bdfb57154b8a11d7f1682ecc0f79abf8e02
-	   ...
+           swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35
+           swh:1:rev:52c90f2d32bfa7d6eccd66a56c44ace1f78fbadd
+           swh:1:rev:cea92e843e40452c08ba313abc39f59efbb4c29c
+           swh:1:rev:8d517bdfb57154b8a11d7f1682ecc0f79abf8e02
+           ...
 
 .. http:get:: /graph/randomwalk/:src/:dst
 
diff --git a/swh/graph/client.py b/swh/graph/client.py
--- a/swh/graph/client.py
+++ b/swh/graph/client.py
@@ -5,7 +5,7 @@
 
 import json
 
-from swh.core.api import RPCClient
+from swh.core.api import RPCClient, RemoteException
 
 
 class GraphAPIError(Exception):
@@ -36,6 +36,24 @@
     def stats(self):
         return self.get('stats')
 
+    def node(self, src):
+        try:
+            list(self.get_lines('node/{}'.format(src)))
+            return True
+        except RemoteException:
+            return False
+
+    def edge(self, src, dst, edges="*", direction="forward"):
+        try:
+            list(self.get_lines('edge/{}/{}'.format(src, dst),
+                                params={
+                                    'edges': edges,
+                                    'direction': direction
+                                }))
+            return True
+        except RemoteException:
+            return False
+
     def leaves(self, src, edges="*", direction="forward"):
         return self.get_lines(
             'leaves/{}'.format(src),
diff --git a/swh/graph/server/app.py b/swh/graph/server/app.py
--- a/swh/graph/server/app.py
+++ b/swh/graph/server/app.py
@@ -105,6 +105,37 @@
             body=f'reverse lookup failed for node id: {node}')
 
 
+async def node(request):
+    """check if a node exists in the graph"""
+    backend = request.app['backend']
+    src = request.match_info['src']
+
+    node_of_pid(src, backend)  # will barf if node doesn't exist
+
+    return aiohttp.web.Response(body=f'{src}', content_type='text/plain')
+
+
+async def edge(request):
+    """check if an edge exists in the graph"""
+    backend = request.app['backend']
+
+    edges = get_edges(request)
+    direction = get_direction(request)
+    src = request.match_info['src']
+    dst = request.match_info['dst']
+    src_node = node_of_pid(src, backend)
+    dst_node = node_of_pid(dst, backend)
+
+    async for res_node in backend.simple_traversal(
+            'neighbors', direction, edges, src_node
+    ):
+        if res_node == dst_node:
+            return aiohttp.web.Response(body=f'{src} {dst}',
+                                        content_type='text/plain')
+
+    raise aiohttp.web.HTTPNotFound(body=f'edge not found: {src} -> {dst}')
+
+
 def get_simple_traversal_handler(ttype):
     async def simple_traversal(request):
         backend = request.app['backend']
@@ -199,6 +230,9 @@
     app.router.add_get('/graph', index)
     app.router.add_get('/graph/stats', stats)
 
+    app.router.add_get('/graph/node/{src}', node)
+    app.router.add_get('/graph/edge/{src}/{dst}', edge)
+
     app.router.add_get('/graph/leaves/{src}',
                        get_simple_traversal_handler('leaves'))
     app.router.add_get('/graph/neighbors/{src}',
diff --git a/swh/graph/tests/test_api_client.py b/swh/graph/tests/test_api_client.py
--- a/swh/graph/tests/test_api_client.py
+++ b/swh/graph/tests/test_api_client.py
@@ -32,6 +32,57 @@
     assert isinstance(stats['outdegree']['avg'], float)
 
 
+def test_node(graph_client):
+    existing_nodes = [
+        'swh:1:cnt:0000000000000000000000000000000000000005',
+        'swh:1:dir:0000000000000000000000000000000000000017',
+        'swh:1:ori:0000000000000000000000000000000000000021',
+        'swh:1:rel:0000000000000000000000000000000000000019',
+        'swh:1:rev:0000000000000000000000000000000000000018',
+        'swh:1:snp:0000000000000000000000000000000000000020',
+    ]
+    non_existing_nodes = [
+        'swh:1:cnt:00f0000000000000000000000000000000000005',
+        'swh:1:dir:000f000000000000000000000000000000000017',
+        'swh:1:ori:0000f00000000000000000000000000000000021',
+        'swh:1:rel:00000f0000000000000000000000000000000019',
+        'swh:1:rev:000000f000000000000000000000000000000018',
+        'swh:1:snp:0000000f00000000000000000000000000000020',
+        'swh:2:inv:00invalidpidbwawaaaaaaa00000000000000020',
+    ]
+    for node in existing_nodes:
+        assert graph_client.node(node)
+    for node in non_existing_nodes:
+        assert not(graph_client.node(node))
+
+
+def test_edge(graph_client):
+    existing_edges = [
+        ('swh:1:dir:0000000000000000000000000000000000000002',
+         'swh:1:cnt:0000000000000000000000000000000000000001'),
+        ('swh:1:rev:0000000000000000000000000000000000000003',
+         'swh:1:dir:0000000000000000000000000000000000000002'),
+        ('swh:1:rev:0000000000000000000000000000000000000009',
+         'swh:1:dir:0000000000000000000000000000000000000008'),
+        ('swh:1:snp:0000000000000000000000000000000000000020',
+         'swh:1:rel:0000000000000000000000000000000000000010'),
+        ('swh:1:ori:0000000000000000000000000000000000000021',
+         'swh:1:snp:0000000000000000000000000000000000000020'),
+    ]
+    non_existing_edges = [
+        ('swh:1:dir:0000000000000000000000000000000000000002',
+         'swh:1:ori:0000000000000000000000000000000000000021'),
+        ('swh:1:rev:0000000000000000000000000000000000000018',
+         'swh:1:cnt:0000000000000000000000000000000000000001'),
+        ('swh:1:ori:0000000000000000000000000000000000000021',
+         'swh:2:inv:00invalidpidbwawaaaaaaa00000000000000020'),
+    ]
+    for (src, dst) in existing_edges:
+        assert graph_client.edge(src, dst)
+    for (src, dst) in non_existing_edges:
+        assert not(graph_client.edge(src, dst))
+
+
 def test_leaves(graph_client):
     actual = list(graph_client.leaves(
         'swh:1:ori:0000000000000000000000000000000000000021'