You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by xi...@apache.org on 2026/06/25 15:20:17 UTC

(tinkerpop) 02/05: Extend multi-label to edges, fix transactions, add feature tests

This is an automated email from the ASF dual-hosted git repository.

xiazcy pushed a commit to branch multi-label-experiment
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git

commit 511dcd9e47abda40675631488f03f41fadc84f61
Author: Yang Xia <xi...@gmail.com>
AuthorDate: Thu Jun 25 02:18:23 2026 -0700

    Extend multi-label to edges, fix transactions, add feature tests
    
    - Implement multi-label for edges with binary and GraphSON support
    - Fix multi-label in TinkerTransactionGraph
    - Add Gherkin feature tests for labels(), addLabel(), dropLabel() steps
    - Add event/mutation support for label changes
    - Thread-safe label storage for edges (ConcurrentHashMap.newKeySet())
    - Wire up GLV test infrastructure for multi-label scenarios
---
 AGENTS.md                                          |  31 +
 .../grammar/DefaultGremlinBaseVisitor.java         |   8 +
 .../language/grammar/TraversalMethodVisitor.java   |  28 +
 .../grammar/TraversalSourceSpawnMethodVisitor.java |  27 +-
 .../traversal/dsl/graph/GraphTraversal.java        |  35 +-
 .../traversal/dsl/graph/GraphTraversalSource.java  |  52 +-
 .../gremlin/process/traversal/dsl/graph/__.java    |   7 +
 .../step/map/AbstractAddEdgeStepPlaceholder.java   |   5 +
 .../map/AbstractAddElementStepPlaceholder.java     |   7 +-
 .../step/map/AbstractAddVertexStepPlaceholder.java |   6 +
 .../traversal/step/map/AddEdgeStartStep.java       |  32 +-
 .../step/map/AddEdgeStartStepPlaceholder.java      |  10 +-
 .../process/traversal/step/map/AddEdgeStep.java    |  32 +-
 .../traversal/step/map/AddEdgeStepPlaceholder.java |  10 +-
 .../traversal/step/map/AddVertexStartStep.java     |  11 +
 .../step/map/AddVertexStartStepPlaceholder.java    |  10 +-
 .../process/traversal/step/map/AddVertexStep.java  |  11 +
 .../step/map/AddVertexStepPlaceholder.java         |  10 +-
 .../process/traversal/step/map/ElementMapStep.java |   6 +-
 .../process/traversal/step/map/MergeEdgeStep.java  | 113 ++-
 .../traversal/step/map/PropertyMapStep.java        |   6 +-
 .../traversal/step/sideEffect/AddLabelStep.java    |  18 +-
 .../traversal/step/sideEffect/DropLabelsStep.java  |  18 +-
 .../process/traversal/step/util/WithOptions.java   |  18 +
 .../process/traversal/step/util/event/Event.java   |  26 +
 .../traversal/step/util/event/EventUtil.java       |  20 +
 .../structure/io/binary/types/EdgeSerializer.java  |  63 +-
 .../io/graphson/GraphSONSerializersV4.java         |  12 +-
 .../structure/util/detached/DetachedEdge.java      |  34 +
 .../structure/util/reference/ReferenceEdge.java    |  31 +
 .../gremlin/structure/util/star/StarGraph.java     |  63 +-
 .../Gherkin/GherkinTestRunner.cs                   |   6 +
 .../Gherkin/IgnoreException.cs                     |   7 +-
 gremlin-go/driver/cucumber/cucumberSteps_test.go   |   1 +
 .../gremlin-javascript/test/cucumber/world.js      |   4 +
 gremlin-language/src/main/antlr4/Gremlin.g4        |   8 +-
 .../src/main/python/tests/feature/feature_steps.py |   4 +
 .../gremlin/language/translator/translations.json  | 878 +++++++++++++++++++++
 .../gremlin/test/features/map/AddVertex.feature    |  25 +-
 .../gremlin/test/features/map/Labels.feature       | 110 +++
 .../gremlin/test/features/map/MergeVertex.feature  | 124 +++
 .../test/features/sideEffect/AddLabel.feature      |  66 ++
 .../test/features/sideEffect/DropLabel.feature     |  83 ++
 .../gremlin/structure/ExceptionCoverageTest.java   |   3 +
 .../tinkergraph/structure/AbstractTinkerGraph.java |  20 +
 .../gremlin/tinkergraph/structure/TinkerEdge.java  |  89 ++-
 .../tinkergraph/structure/TinkerElement.java       |   2 +-
 .../gremlin/tinkergraph/structure/TinkerGraph.java |  30 +
 .../structure/TinkerTransactionGraph.java          |  39 +-
 .../tinkergraph/structure/TinkerVertex.java        |  33 +-
 .../step/sideEffect/LabelMutationStepTest.java     |  16 +-
 .../structure/TinkerVertexMultiLabelTest.java      |  12 +-
 52 files changed, 2193 insertions(+), 127 deletions(-)

diff --git a/AGENTS.md b/AGENTS.md
index f4952c7666..f03a28338a 100644
--- a/AGENTS.md
+++ b/AGENTS.md
@@ -97,3 +97,34 @@ These rules apply to any AI/IDE assistant operating on this repository.
 
 1. Prefer no change over an unsafe or speculative change.
 2. Ask for clarification.
+
+## Beads Issue Tracker
+
+This project uses **bd (beads)** for issue tracking. Run `bd prime` to see full workflow context and commands.
+
+### Quick Reference
+
+```bash
+bd ready              # Find available work
+bd show <id>          # View issue details
+bd update <id> --claim  # Claim work
+bd close <id>         # Complete work
+```
+
+### Rules
+
+- Use `bd` for ALL task tracking — do NOT use TodoWrite, TaskCreate, or markdown TODO lists
+- Run `bd prime` for detailed command reference and session close protocol
+- Use `bd remember` for persistent knowledge — do NOT use MEMORY.md files
+
+**Architecture in one line:** issues live in a local Dolt DB; sync uses `refs/dolt/data` on your git remote; `.beads/issues.jsonl` is a passive export. See https://github.com/gastownhall/beads/blob/main/docs/SYNC_CONCEPTS.md for details and anti-patterns.
+
+## Session Completion
+
+**When ending a work session**, you MUST complete ALL steps below.
+
+**MANDATORY WORKFLOW:**
+
+1. **File issues for remaining work** - Create issues for anything that needs follow-up
+2. **Run quality gates** (if code changed) - Tests, linters, builds
+3. **Update issue status** - Close finished work, update in-progress items
\ No newline at end of file
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/DefaultGremlinBaseVisitor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/DefaultGremlinBaseVisitor.java
index 10a35ec518..02fa82e925 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/DefaultGremlinBaseVisitor.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/DefaultGremlinBaseVisitor.java
@@ -167,6 +167,14 @@ public class DefaultGremlinBaseVisitor<T> extends AbstractParseTreeVisitor<T> im
 	 * {@inheritDoc}
 	 */
 	@Override public T visitTraversalMethod_addE_String(final GremlinParser.TraversalMethod_addE_StringContext ctx) { notImplemented(ctx); return null; }
+	/**
+	 * {@inheritDoc}
+	 */
+	@Override public T visitTraversalMethod_addE_StringVarargs(final GremlinParser.TraversalMethod_addE_StringVarargsContext ctx) { notImplemented(ctx); return null; }
+	/**
+	 * {@inheritDoc}
+	 */
+	@Override public T visitTraversalMethod_addE_Empty(final GremlinParser.TraversalMethod_addE_EmptyContext ctx) { notImplemented(ctx); return null; }
 	/**
 	 * {@inheritDoc}
 	 */
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalMethodVisitor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalMethodVisitor.java
index 216af370b4..f99ce7f4b8 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalMethodVisitor.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalMethodVisitor.java
@@ -30,6 +30,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 import org.apache.tinkerpop.gremlin.structure.Column;
 import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Edge;
 import org.apache.tinkerpop.gremlin.structure.T;
 import org.apache.tinkerpop.gremlin.structure.VertexProperty.Cardinality;
 
@@ -204,6 +205,33 @@ public class TraversalMethodVisitor extends TraversalRootVisitor<GraphTraversal>
         }
     }
 
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public GraphTraversal visitTraversalMethod_addE_StringVarargs(final GremlinParser.TraversalMethod_addE_StringVarargsContext ctx) {
+        final List<GremlinParser.StringArgumentContext> args = ctx.stringArgument();
+        final Object firstLiteralOrVar = antlr.argumentVisitor.visitStringArgument(args.get(0));
+        final String firstLabel = firstLiteralOrVar instanceof String ? (String) firstLiteralOrVar : ((GValue<String>) firstLiteralOrVar).get();
+        final Object secondLiteralOrVar = antlr.argumentVisitor.visitStringArgument(args.get(1));
+        final String secondLabel = secondLiteralOrVar instanceof String ? (String) secondLiteralOrVar : ((GValue<String>) secondLiteralOrVar).get();
+
+        final String[] moreLabels = new String[args.size() - 2];
+        for (int i = 2; i < args.size(); i++) {
+            final Object literalOrVar = antlr.argumentVisitor.visitStringArgument(args.get(i));
+            moreLabels[i - 2] = literalOrVar instanceof String ? (String) literalOrVar : ((GValue<String>) literalOrVar).get();
+        }
+        return this.graphTraversal.addE(firstLabel, secondLabel, moreLabels);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public GraphTraversal visitTraversalMethod_addE_Empty(final GremlinParser.TraversalMethod_addE_EmptyContext ctx) {
+        return this.graphTraversal.addE(Edge.DEFAULT_LABEL);
+    }
+
     /**
      * {@inheritDoc}
      */
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalSourceSpawnMethodVisitor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalSourceSpawnMethodVisitor.java
index 9ac0e9a3fe..c07c1b21b9 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalSourceSpawnMethodVisitor.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/language/grammar/TraversalSourceSpawnMethodVisitor.java
@@ -57,17 +57,32 @@ public class TraversalSourceSpawnMethodVisitor extends DefaultGremlinBaseVisitor
      */
     @Override
     public GraphTraversal visitTraversalSourceSpawnMethod_addE(final GremlinParser.TraversalSourceSpawnMethod_addEContext ctx) {
-        if (ctx.stringArgument() != null) {
-            final Object literalOrVar = antlr.argumentVisitor.visitStringArgument(ctx.stringArgument());
-            if (GValue.valueInstanceOf(literalOrVar, String.class)) {
-                return this.traversalSource.addE((GValue<String>) literalOrVar);
+        final List<GremlinParser.StringArgumentContext> stringArgs = ctx.stringArgument();
+        if (stringArgs != null && !stringArgs.isEmpty()) {
+            if (stringArgs.size() == 1) {
+                final Object literalOrVar = antlr.argumentVisitor.visitStringArgument(stringArgs.get(0));
+                if (GValue.valueInstanceOf(literalOrVar, String.class)) {
+                    return this.traversalSource.addE((GValue<String>) literalOrVar);
+                } else {
+                    return this.traversalSource.addE((String) literalOrVar);
+                }
             } else {
-                return this.traversalSource.addE((String) literalOrVar);
+                // Multi-label: addE("a", "b", ...)
+                final Object firstLiteralOrVar = antlr.argumentVisitor.visitStringArgument(stringArgs.get(0));
+                final String firstLabel = firstLiteralOrVar instanceof String ? (String) firstLiteralOrVar : ((GValue<String>) firstLiteralOrVar).get();
+                final Object secondLiteralOrVar = antlr.argumentVisitor.visitStringArgument(stringArgs.get(1));
+                final String secondLabel = secondLiteralOrVar instanceof String ? (String) secondLiteralOrVar : ((GValue<String>) secondLiteralOrVar).get();
+                final String[] moreLabels = new String[stringArgs.size() - 2];
+                for (int i = 2; i < stringArgs.size(); i++) {
+                    final Object literalOrVar = antlr.argumentVisitor.visitStringArgument(stringArgs.get(i));
+                    moreLabels[i - 2] = literalOrVar instanceof String ? (String) literalOrVar : ((GValue<String>) literalOrVar).get();
+                }
+                return this.traversalSource.addE(firstLabel, secondLabel, moreLabels);
             }
         } else if (ctx.nestedTraversal() != null) {
             return this.traversalSource.addE(anonymousVisitor.visitNestedTraversal(ctx.nestedTraversal()));
         } else {
-            throw new IllegalArgumentException("addE with empty arguments is not valid.");
+            return this.traversalSource.addE();
         }
     }
 
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
index 72f08763d1..b402e506a8 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
@@ -235,6 +235,7 @@ import java.util.Comparator;
 import java.util.Date;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Optional;
@@ -1500,12 +1501,11 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
             if (null == l) throw new IllegalArgumentException("vertexLabel cannot be null");
         }
         this.asAdmin().getGremlinLang().addStep(Symbols.addV, label1, label2, moreLabels);
-        this.asAdmin().addStep(new AddVertexStepPlaceholder<>(this.asAdmin(), label1));
-        // Add the AddLabelStep directly to avoid double-recording in GremlinLang.
-        // The addV step above already recorded all labels; calling t.addLabel() would
-        // record an additional addLabel() step in GremlinLang, producing incorrect output
-        // like g.addV("a","b").addLabel("b") instead of g.addV("a","b").
-        return this.asAdmin().addStep(new AddLabelStep<>(this.asAdmin(), label2, moreLabels));
+        final Set<String> allLabels = new LinkedHashSet<>();
+        allLabels.add(label1);
+        allLabels.add(label2);
+        Collections.addAll(allLabels, moreLabels);
+        return this.asAdmin().addStep(new AddVertexStepPlaceholder<>(this.asAdmin(), allLabels));
     }
 
     /**
@@ -1665,6 +1665,29 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
         return this.asAdmin().addStep(step);
     }
 
+    /**
+     * Multi-label edge creation.
+     *
+     * @param label1     the first label
+     * @param label2     the second label
+     * @param moreLabels additional labels
+     * @return the traversal with the {@link AddEdgeStepContract} added
+     * @since 4.0.0
+     */
+    public default GraphTraversal<S, Edge> addE(final String label1, final String label2, final String... moreLabels) {
+        if (null == label1) throw new IllegalArgumentException("edgeLabel cannot be null");
+        if (null == label2) throw new IllegalArgumentException("edgeLabel cannot be null");
+        for (final String l : moreLabels) {
+            if (null == l) throw new IllegalArgumentException("edgeLabel cannot be null");
+        }
+        this.asAdmin().getGremlinLang().addStep(Symbols.addE, label1, label2, moreLabels);
+        final Set<String> allLabels = new LinkedHashSet<>();
+        allLabels.add(label1);
+        allLabels.add(label2);
+        Collections.addAll(allLabels, moreLabels);
+        return this.asAdmin().addStep(new AddEdgeStepPlaceholder<>(this.asAdmin(), allLabels));
+    }
+
     /**
      * Provide {@code from()}-modulation to respective steps.
      *
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java
index 0c7715f5af..196019a539 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java
@@ -31,7 +31,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 import org.apache.tinkerpop.gremlin.process.traversal.step.branch.UnionStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.AddEdgeStartStepPlaceholder;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.AddVertexStartStepPlaceholder;
-import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.AddLabelStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.CallStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.CallStepPlaceholder;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.DeclarativeMatchStep;
@@ -54,9 +53,12 @@ import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
 import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph;
 
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.Optional;
+import java.util.Set;
 import java.util.function.BinaryOperator;
 import java.util.function.Supplier;
 import java.util.function.UnaryOperator;
@@ -387,12 +389,11 @@ public class GraphTraversalSource implements TraversalSource {
         final GraphTraversalSource clone = this.clone();
         clone.gremlinLang.addStep(GraphTraversal.Symbols.addV, label1, label2, moreLabels);
         final GraphTraversal.Admin<Vertex, Vertex> traversal = new DefaultGraphTraversal<>(clone);
-        traversal.addStep(new AddVertexStartStepPlaceholder(traversal, label1));
-        // Add the AddLabelStep directly to avoid double-recording in GremlinLang.
-        // The addV step above already recorded all labels; calling t.addLabel() would
-        // record an additional addLabel() step in GremlinLang, producing incorrect output
-        // like g.addV("a","b").addLabel("b") instead of g.addV("a","b").
-        return traversal.addStep(new AddLabelStep<>(traversal, label2, moreLabels));
+        final Set<String> allLabels = new LinkedHashSet<>();
+        allLabels.add(label1);
+        allLabels.add(label2);
+        Collections.addAll(allLabels, moreLabels);
+        return traversal.addStep(new AddVertexStartStepPlaceholder(traversal, allLabels));
     }
 
     /**
@@ -431,6 +432,43 @@ public class GraphTraversalSource implements TraversalSource {
         return traversal.addStep(new AddEdgeStartStepPlaceholder(traversal, label));
     }
 
+    /**
+     * Spawns a {@link GraphTraversal} by adding an edge with multiple labels.
+     *
+     * @param label1     the first label
+     * @param label2     the second label
+     * @param moreLabels additional labels
+     * @return the traversal with the edge added
+     * @since 4.0.0
+     */
+    public GraphTraversal<Edge, Edge> addE(final String label1, final String label2, final String... moreLabels) {
+        if (null == label1) throw new IllegalArgumentException("edgeLabel cannot be null");
+        if (null == label2) throw new IllegalArgumentException("edgeLabel cannot be null");
+        for (final String l : moreLabels) {
+            if (null == l) throw new IllegalArgumentException("edgeLabel cannot be null");
+        }
+        final GraphTraversalSource clone = this.clone();
+        clone.gremlinLang.addStep(GraphTraversal.Symbols.addE, label1, label2, moreLabels);
+        final GraphTraversal.Admin<Edge, Edge> traversal = new DefaultGraphTraversal<>(clone);
+        final Set<String> allLabels = new LinkedHashSet<>();
+        allLabels.add(label1);
+        allLabels.add(label2);
+        Collections.addAll(allLabels, moreLabels);
+        return traversal.addStep(new AddEdgeStartStepPlaceholder(traversal, allLabels));
+    }
+
+    /**
+     * Spawns a {@link GraphTraversal} by adding an edge with the provider's default label.
+     *
+     * @since 4.0.0
+     */
+    public GraphTraversal<Edge, Edge> addE() {
+        final GraphTraversalSource clone = this.clone();
+        clone.gremlinLang.addStep(GraphTraversal.Symbols.addE);
+        final GraphTraversal.Admin<Edge, Edge> traversal = new DefaultGraphTraversal<>(clone);
+        return traversal.addStep(new AddEdgeStartStepPlaceholder(traversal, (String) null));
+    }
+
     /**
      * Spawns a {@link GraphTraversal} by doing a merge (i.e. upsert) style operation for an {@link Vertex} using a
      * {@code Map} as an argument. The {@code Map} represents search criteria and will match each of the supplied
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
index 421a1f33ad..506bc4e91f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
@@ -756,6 +756,13 @@ public class __ {
         return __.<A>start().addE(edgeLabel);
     }
 
+    /**
+     * @see GraphTraversal#addE(String, String, String...)
+     */
+    public static <A> GraphTraversal<A, Edge> addE(final String label1, final String label2, final String... moreLabels) {
+        return __.<A>start().addE(label1, label2, moreLabels);
+    }
+
     /**
      * @see GraphTraversal#addE(GValue)
      */
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddEdgeStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddEdgeStepPlaceholder.java
index fb1ce7e8c9..95d377c317 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddEdgeStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddEdgeStepPlaceholder.java
@@ -29,6 +29,7 @@ import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceVertex;
 import java.util.Collection;
 import java.util.List;
 import java.util.Objects;
+import java.util.Set;
 
 public abstract class AbstractAddEdgeStepPlaceholder<S> extends AbstractAddElementStepPlaceholder<S, Edge, Event.EdgeAddedEvent> implements AddEdgeStepContract<S> {
     protected Traversal.Admin<?, ?> from;
@@ -42,6 +43,10 @@ public abstract class AbstractAddEdgeStepPlaceholder<S> extends AbstractAddEleme
         super(traversal, label);
     }
 
+    public AbstractAddEdgeStepPlaceholder(Traversal.Admin traversal, Set<String> labels) {
+        super(traversal, labels);
+    }
+
     public AbstractAddEdgeStepPlaceholder(Traversal.Admin traversal, Traversal.Admin<S, String> labelTraversal) {
         super(traversal, labelTraversal);
     }
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddElementStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddElementStepPlaceholder.java
index 830fef2c80..a2015b4613 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddElementStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddElementStepPlaceholder.java
@@ -61,7 +61,7 @@ public abstract class AbstractAddElementStepPlaceholder<S, E extends Element, X
     protected AbstractAddElementStepPlaceholder(final Traversal.Admin traversal, final GValue<String> label) {
         super(traversal);
         this.label = label == null ? this.getDefaultLabel() : label;
-        if (label.isVariable()) {
+        if (label != null && label.isVariable()) {
             traversal.getGValueManager().register(label);
         }
     }
@@ -75,6 +75,11 @@ public abstract class AbstractAddElementStepPlaceholder<S, E extends Element, X
         addTraversal(labelTraversal);
     }
 
+    protected AbstractAddElementStepPlaceholder(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal);
+        this.label = (labels == null || labels.isEmpty()) ? this.getDefaultLabel() : labels;
+    }
+
     protected abstract String getDefaultLabel();
 
     @Override
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddVertexStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddVertexStepPlaceholder.java
index 66aa3df116..3e0f0c1c0f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddVertexStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AbstractAddVertexStepPlaceholder.java
@@ -25,6 +25,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event;
 import org.apache.tinkerpop.gremlin.structure.Vertex;
 
 import java.util.Objects;
+import java.util.Set;
 
 public abstract class AbstractAddVertexStepPlaceholder<S> extends AbstractAddElementStepPlaceholder<S, Vertex, Event.VertexAddedEvent>
         implements AddVertexStepContract<S>, GValueHolder<S, Vertex> {
@@ -46,6 +47,11 @@ public abstract class AbstractAddVertexStepPlaceholder<S> extends AbstractAddEle
         userProvidedLabel = vertexLabelTraversal != null;
     }
 
+    protected AbstractAddVertexStepPlaceholder(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal, labels);
+        userProvidedLabel = labels != null && !labels.isEmpty();
+    }
+
     @Override
     protected String getDefaultLabel() {
         return Vertex.DEFAULT_LABEL;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStep.java
index 628587a509..99ccd7ce9e 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStep.java
@@ -19,7 +19,10 @@
 
 package org.apache.tinkerpop.gremlin.process.traversal.step.map;
 
+import java.util.Arrays;
 import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -67,6 +70,15 @@ public class AddEdgeStartStep extends AbstractStep<Edge, Edge> implements AddEdg
         this.internalParameters.set(this, T.label, edgeLabelTraversal);
     }
 
+    public AddEdgeStartStep(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal);
+        if (labels == null || labels.isEmpty()) {
+            this.internalParameters.set(this, T.label, Edge.DEFAULT_LABEL);
+        } else {
+            this.internalParameters.set(this, T.label, labels);
+        }
+    }
+
     @Override
     public <S, E> List<Traversal.Admin<S, E>> getLocalChildren() {
         return this.internalParameters.getTraversals();
@@ -121,7 +133,21 @@ public class AddEdgeStartStep extends AbstractStep<Edge, Edge> implements AddEdg
             // a dead traverser to trigger the traversal
             final Traverser.Admin traverser = generator.generate(1, (Step) this, 1);
 
-            final String edgeLabel = (String) this.internalParameters.get(traverser, T.label, () -> Edge.DEFAULT_LABEL).get(0);
+            final Object labelParam = this.internalParameters.get(traverser, T.label, () -> Edge.DEFAULT_LABEL).get(0);
+            final String edgeLabel;
+            final Set<String> additionalLabels;
+            if (labelParam instanceof Set) {
+                final Set<String> labelSet = (Set<String>) labelParam;
+                final Iterator<String> iter = labelSet.iterator();
+                edgeLabel = iter.next();
+                additionalLabels = new LinkedHashSet<>();
+                while (iter.hasNext()) {
+                    additionalLabels.add(iter.next());
+                }
+            } else {
+                edgeLabel = (String) labelParam;
+                additionalLabels = Collections.emptySet();
+            }
 
             // FROM/TO must be set and must be vertices
             Object theTo = this.internalParameters.get(traverser, TO, () -> null).get(0);
@@ -165,6 +191,10 @@ public class AddEdgeStartStep extends AbstractStep<Edge, Edge> implements AddEdg
             }
 
             final Edge edge = fromVertex.addEdge(edgeLabel, toVertex, this.internalParameters.getKeyValues(traverser, TO, FROM, T.label));
+            if (!additionalLabels.isEmpty()) {
+                final String[] extra = additionalLabels.toArray(new String[0]);
+                edge.addLabel(extra[0], Arrays.copyOfRange(extra, 1, extra.length));
+            }
             EventUtil.registerEdgeCreation(callbackRegistry, getTraversal(), edge);
             return generator.generate(edge, this, 1L);
         } else
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStepPlaceholder.java
index 6042823e17..bbf4d429f3 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStartStepPlaceholder.java
@@ -24,6 +24,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.GValueConstantTrave
 import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 import org.apache.tinkerpop.gremlin.structure.Edge;
 
+import java.util.Set;
+
 public class AddEdgeStartStepPlaceholder extends AbstractAddEdgeStepPlaceholder<Edge> {
 
     public AddEdgeStartStepPlaceholder(final Traversal.Admin traversal, final String edgeLabel) {
@@ -40,10 +42,16 @@ public class AddEdgeStartStepPlaceholder extends AbstractAddEdgeStepPlaceholder<
                 (Traversal.Admin<Edge, String>) edgeLabelTraversal);
     }
 
+    public AddEdgeStartStepPlaceholder(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal, labels);
+    }
+
     @Override
     public AddEdgeStartStep asConcreteStep() {
         AddEdgeStartStep step;
-        if (label instanceof Traversal) {
+        if (label instanceof Set) {
+            step = new AddEdgeStartStep(traversal, (Set<String>) label);
+        } else if (label instanceof Traversal) {
             step = new AddEdgeStartStep(traversal, ((Traversal<?, String>) label).asAdmin());
         } else if (label instanceof GValue) {
             step = new AddEdgeStartStep(traversal, ((GValue<String>) label).get());
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStep.java
index 753d9ae993..7073a7e80f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStep.java
@@ -18,7 +18,10 @@
  */
 package org.apache.tinkerpop.gremlin.process.traversal.step.map;
 
+import java.util.Arrays;
 import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -62,6 +65,15 @@ public class AddEdgeStep<S> extends ScalarMapStep<S, Edge> implements AddEdgeSte
         this.internalParameters.set(this, T.label, edgeLabelTraversal);
     }
 
+    public AddEdgeStep(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal);
+        if (labels == null || labels.isEmpty()) {
+            this.internalParameters.set(this, T.label, Edge.DEFAULT_LABEL);
+        } else {
+            this.internalParameters.set(this, T.label, labels);
+        }
+    }
+
     @Override
     public <S, E> List<Traversal.Admin<S, E>> getLocalChildren() {
         return this.internalParameters.getTraversals();
@@ -109,7 +121,21 @@ public class AddEdgeStep<S> extends ScalarMapStep<S, Edge> implements AddEdgeSte
 
     @Override
     protected Edge map(final Traverser.Admin<S> traverser) {
-        final String edgeLabel = this.internalParameters.get(traverser, T.label, () -> Edge.DEFAULT_LABEL).get(0);
+        final Object labelParam = this.internalParameters.get(traverser, T.label, () -> Edge.DEFAULT_LABEL).get(0);
+        final String edgeLabel;
+        final Set<String> additionalLabels;
+        if (labelParam instanceof Set) {
+            final Set<String> labelSet = (Set<String>) labelParam;
+            final Iterator<String> iter = labelSet.iterator();
+            edgeLabel = iter.next();
+            additionalLabels = new LinkedHashSet<>();
+            while (iter.hasNext()) {
+                additionalLabels.add(iter.next());
+            }
+        } else {
+            edgeLabel = (String) labelParam;
+            additionalLabels = Collections.emptySet();
+        }
 
         Vertex toVertex = getAdjacentVertex(this.internalParameters, TO, traverser, edgeLabel);
         Vertex fromVertex = getAdjacentVertex(this.internalParameters, FROM, traverser, edgeLabel);
@@ -135,6 +161,10 @@ public class AddEdgeStep<S> extends ScalarMapStep<S, Edge> implements AddEdgeSte
         }
 
         final Edge edge = fromVertex.addEdge(edgeLabel, toVertex, this.internalParameters.getKeyValues(traverser, TO, FROM, T.label));
+        if (!additionalLabels.isEmpty()) {
+            final String[] extra = additionalLabels.toArray(new String[0]);
+            edge.addLabel(extra[0], Arrays.copyOfRange(extra, 1, extra.length));
+        }
         EventUtil.registerEdgeCreation(callbackRegistry, getTraversal(), edge);
         return edge;
     }
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
index a6a5a4466a..a992a1314a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
@@ -24,6 +24,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.GValueConstantTrave
 import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 import org.apache.tinkerpop.gremlin.structure.Edge;
 
+import java.util.Set;
+
 public class AddEdgeStepPlaceholder<S> extends AbstractAddEdgeStepPlaceholder<S> {
 
     public AddEdgeStepPlaceholder(final Traversal.Admin traversal, final String edgeLabel) {
@@ -39,10 +41,16 @@ public class AddEdgeStepPlaceholder<S> extends AbstractAddEdgeStepPlaceholder<S>
                 new ConstantTraversal<>(Edge.DEFAULT_LABEL) : edgeLabelTraversal);
     }
 
+    public AddEdgeStepPlaceholder(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal, labels);
+    }
+
     @Override
     public AddEdgeStep<S> asConcreteStep() {
         AddEdgeStep<S> step;
-        if (label instanceof Traversal) {
+        if (label instanceof Set) {
+            step = new AddEdgeStep<>(traversal, (Set<String>) label);
+        } else if (label instanceof Traversal) {
             step = new AddEdgeStep<>(traversal, ((Traversal<S, String>) label).asAdmin());
         } else if (label instanceof GValue) {
             step = new AddEdgeStep<>(traversal, ((GValue<String>) label).get());
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStep.java
index 7718cc2883..5f109ae426 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStep.java
@@ -63,6 +63,17 @@ public class AddVertexStartStep extends AbstractStep<Vertex, Vertex> implements
         userProvidedLabel = vertexLabelTraversal != null;
     }
 
+    public AddVertexStartStep(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal);
+        if (labels == null || labels.isEmpty()) {
+            this.internalParameters.set(this, T.label, Vertex.DEFAULT_LABEL);
+            userProvidedLabel = false;
+        } else {
+            this.internalParameters.set(this, T.label, labels);
+            userProvidedLabel = true;
+        }
+    }
+
     @Override
     public boolean hasUserProvidedLabel() {
         return userProvidedLabel;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStepPlaceholder.java
index e84f4a7f1c..a1b5fa2449 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStartStepPlaceholder.java
@@ -24,6 +24,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 import org.apache.tinkerpop.gremlin.process.traversal.step.GValueHolder;
 import org.apache.tinkerpop.gremlin.structure.Vertex;
 
+import java.util.Set;
+
 public class AddVertexStartStepPlaceholder extends AbstractAddVertexStepPlaceholder<Vertex>
         implements AddVertexStepContract<Vertex>, GValueHolder<Vertex, Vertex> {
 
@@ -40,10 +42,16 @@ public class AddVertexStartStepPlaceholder extends AbstractAddVertexStepPlacehol
                 new ConstantTraversal<>(Vertex.DEFAULT_LABEL) : (Traversal.Admin<Vertex,String>) vertexLabelTraversal);
     }
 
+    public AddVertexStartStepPlaceholder(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal, labels);
+    }
+
     @Override
     public AddVertexStartStep asConcreteStep() {
         AddVertexStartStep step;
-        if (label instanceof Traversal) {
+        if (label instanceof Set) {
+            step = new AddVertexStartStep(traversal, (Set<String>) label);
+        } else if (label instanceof Traversal) {
             step = new AddVertexStartStep(traversal, ((Traversal<?, String>) label).asAdmin());
         } else if (label instanceof GValue) {
             step = new AddVertexStartStep(traversal, ((GValue<String>) label).get());
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStep.java
index b015920e17..4c2b505b53 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStep.java
@@ -59,6 +59,17 @@ public class AddVertexStep<S> extends ScalarMapStep<S, Vertex> implements AddVer
         userProvidedLabel = vertexLabelTraversal != null;
     }
 
+    public AddVertexStep(final Traversal.Admin traversal, final Set<String> labels) {
+        super(traversal);
+        if (labels == null || labels.isEmpty()) {
+            this.internalParameters.set(this, T.label, Vertex.DEFAULT_LABEL);
+            userProvidedLabel = false;
+        } else {
+            this.internalParameters.set(this, T.label, labels);
+            userProvidedLabel = true;
+        }
+    }
+
     @Override
     public boolean hasUserProvidedLabel() {
         return userProvidedLabel;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStepPlaceholder.java
index 505bc47c1f..b749760051 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddVertexStepPlaceholder.java
@@ -22,6 +22,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 import org.apache.tinkerpop.gremlin.process.traversal.lambda.GValueConstantTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
 
+import java.util.Set;
+
 public class AddVertexStepPlaceholder<S> extends AbstractAddVertexStepPlaceholder<S> {
 
     public AddVertexStepPlaceholder(Traversal.Admin traversal, String label) {
@@ -36,10 +38,16 @@ public class AddVertexStepPlaceholder<S> extends AbstractAddVertexStepPlaceholde
         super(traversal, vertexLabelTraversal);
     }
 
+    public AddVertexStepPlaceholder(Traversal.Admin traversal, Set<String> labels) {
+        super(traversal, labels);
+    }
+
     @Override
     public AddVertexStep<S> asConcreteStep() {
         AddVertexStep<S> step;
-        if (label instanceof Traversal) {
+        if (label instanceof Set) {
+            step = new AddVertexStep<>(traversal, (Set<String>) label);
+        } else if (label instanceof Traversal) {
             step = new AddVertexStep<>(traversal, ((Traversal<S, String>) label).asAdmin());
         } else if (label instanceof GValue) {
             step = new AddVertexStep<>(traversal, ((GValue<String>) label).get());
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ElementMapStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ElementMapStep.java
index 370b0cd059..b05e620849 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ElementMapStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ElementMapStep.java
@@ -25,7 +25,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GraphComputing;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.WithOptions;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.OptionsStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.structure.Direction;
 import org.apache.tinkerpop.gremlin.structure.Edge;
@@ -131,10 +130,7 @@ public class ElementMapStep<K,E> extends ScalarMapStep<Element, Map<K, E>> imple
      * or source-level {@code g.with("multilabel")}.
      */
     private boolean isMultilabelEnabled() {
-        if (this.multilabel) return true;
-        return getTraversal().getStrategies().getStrategy(OptionsStrategy.class)
-                .map(os -> os.getOptions().containsKey("multilabel") || os.getOptions().containsKey(WithOptions.multilabel))
-                .orElse(false);
+        return WithOptions.isMultilabelEnabled(this.multilabel, getTraversal());
     }
 
     public String[] getPropertyKeys() {
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MergeEdgeStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MergeEdgeStep.java
index 3535143192..261ab78eb8 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MergeEdgeStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MergeEdgeStep.java
@@ -20,6 +20,7 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map;
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
@@ -166,17 +167,21 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
         final Graph graph = getGraph();
 
         final Object edgeId = search.get(T.id);
-        final String edgeLabel = (String) search.get(T.label);
+        final Object labelValue = search.get(T.label);
         final Object fromId = search.get(Direction.OUT);
         final Object toId = search.get(Direction.IN);
 
+        // Extract a single label string for use in outE(label)/inE(label) calls.
+        // For multi-label (collection), we use hasLabel() chaining instead.
+        final String singleLabel = labelValue instanceof String ? (String) labelValue : null;
+        final boolean hasLabelConstraint = labelValue != null;
+
         GraphTraversal t;
         if (edgeId != null) {
 
             // g.E(eid).hasLabel(label).where(outV().hasId(fromId)).where(inV().hasId(toId));
             t = graph.traversal().E(edgeId);
-            if (edgeLabel != null)
-                t = t.hasLabel(edgeLabel);
+            t = applyLabelConstraint(t, labelValue);
             if (fromId != null)
                 t = t.where(outV().hasId(fromId));
             if (toId != null)
@@ -186,10 +191,14 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
 
             // g.V(fromId).outE(label).where(inV().hasId(toId));
             t = graph.traversal().V(fromId);
-            if (edgeLabel != null)
-                t = t.outE(edgeLabel);
-            else
+            if (singleLabel != null)
+                t = t.outE(singleLabel);
+            else {
                 t = t.outE();
+                // apply multi-label constraint after outE() if it's a collection
+                if (hasLabelConstraint && singleLabel == null)
+                    t = applyLabelConstraint(t, labelValue);
+            }
             if (toId != null)
                 t = t.where(inV().hasId(toId));
 
@@ -197,17 +206,20 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
 
             // g.V(toId).inE(edgeLabel);
             t = graph.traversal().V(toId);
-            if (edgeLabel != null)
-                t = t.inE(edgeLabel);
-            else
+            if (singleLabel != null)
+                t = t.inE(singleLabel);
+            else {
                 t = t.inE();
+                // apply multi-label constraint after inE() if it's a collection
+                if (hasLabelConstraint && singleLabel == null)
+                    t = applyLabelConstraint(t, labelValue);
+            }
 
         } else {
 
             // g.E().hasLabel(label)
             t = graph.traversal().E();
-            if (edgeLabel != null)
-                t = t.hasLabel(edgeLabel);
+            t = applyLabelConstraint(t, labelValue);
 
         }
 
@@ -222,6 +234,26 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
         return CloseableIterator.of(t);
     }
 
+    /**
+     * Apply label constraint(s) to the traversal. Supports both single String labels and
+     * Collection labels with AND semantics (edge must have ALL specified labels).
+     */
+    protected GraphTraversal applyLabelConstraint(GraphTraversal t, final Object labelValue) {
+        if (labelValue == null) {
+            return t;
+        }
+        if (labelValue instanceof String) {
+            return t.hasLabel((String) labelValue);
+        } else if (labelValue instanceof java.util.Collection) {
+            // Multi-label: AND semantics - must have ALL specified labels
+            for (final Object label : (java.util.Collection<?>) labelValue) {
+                t = t.hasLabel((String) label);
+            }
+            return t;
+        }
+        return t;
+    }
+
     protected Map<?,?> resolveVertices(final Map map, final Traverser.Admin<S> traverser) {
         resolveVertex(Merge.outV, Direction.OUT, map, traverser, outVTraversal);
         resolveVertex(Merge.inV, Direction.IN, map, traverser, inVTraversal);
@@ -279,14 +311,34 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
                 traverser.set((S) e);
 
                 // assume good input from GraphTraversal - folks might drop in a T here even though it is immutable
-                final Map<String, ?> onMatchMap = materializeMap(traverser, onMatchTraversal);
+                final Map onMatchMap = materializeMap(traverser, onMatchTraversal);
                 validateMapInput(onMatchMap, true);
 
                 onMatchMap.forEach((key, value) -> {
+                    // Handle T.label replacement for multi-label support
+                    if (T.label.equals(key) || T.label.getAccessor().equals(key)) {
+                        // Drop all existing labels and replace with new ones
+                        e.dropLabels();
+                        if (value instanceof String) {
+                            e.addLabel((String) value);
+                        } else if (value instanceof java.util.Collection) {
+                            final java.util.Collection<?> labels = (java.util.Collection<?>) value;
+                            if (!labels.isEmpty()) {
+                                final String[] labelArray = labels.stream()
+                                        .map(l -> (String) l)
+                                        .toArray(String[]::new);
+                                e.addLabel(labelArray[0],
+                                        Arrays.copyOfRange(labelArray, 1, labelArray.length));
+                            }
+                            // Empty collection = use default label behavior (already handled by dropLabels())
+                        }
+                        return;
+                    }
+
                     // trigger callbacks for eventing - in this case, it's a EdgePropertyChangedEvent. if there's no
                     // registry/callbacks then just set the property
-                    EventUtil.registerEdgePropertyChange(callbackRegistry, getTraversal(), e, key, value);
-                    e.property(key, value);
+                    EventUtil.registerEdgePropertyChange(callbackRegistry, getTraversal(), e, (String) key, value);
+                    e.property((String) key, value);
                 });
 
             });
@@ -317,7 +369,30 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
 
         final Vertex fromV = resolveVertex(onCreateMap.get(Direction.OUT));
         final Vertex toV = resolveVertex(onCreateMap.get(Direction.IN));
-        final String label = (String) onCreateMap.getOrDefault(T.label, Edge.DEFAULT_LABEL);
+        final Object labelValue = onCreateMap.getOrDefault(T.label, Edge.DEFAULT_LABEL);
+        final String primaryLabel;
+        final java.util.Collection<String> additionalLabels;
+
+        if (labelValue instanceof String) {
+            primaryLabel = (String) labelValue;
+            additionalLabels = Collections.emptyList();
+        } else if (labelValue instanceof java.util.Collection) {
+            final java.util.Collection<?> labelCollection = (java.util.Collection<?>) labelValue;
+            if (labelCollection.isEmpty()) {
+                primaryLabel = Edge.DEFAULT_LABEL;
+                additionalLabels = Collections.emptyList();
+            } else {
+                final Iterator<?> iter = labelCollection.iterator();
+                primaryLabel = (String) iter.next();
+                additionalLabels = new ArrayList<>();
+                while (iter.hasNext()) {
+                    additionalLabels.add((String) iter.next());
+                }
+            }
+        } else {
+            primaryLabel = Edge.DEFAULT_LABEL;
+            additionalLabels = Collections.emptyList();
+        }
 
         final List<Object> properties = new ArrayList<>();
 
@@ -329,7 +404,13 @@ public class MergeEdgeStep<S> extends MergeElementStep<S, Edge, Map<Object, Obje
             properties.add(e.getValue());
         }
 
-        final Edge edge = fromV.addEdge(label, toV, properties.toArray());
+        final Edge edge = fromV.addEdge(primaryLabel, toV, properties.toArray());
+
+        // add any additional labels from a multi-label collection
+        if (!additionalLabels.isEmpty()) {
+            final String[] extraLabels = additionalLabels.toArray(new String[0]);
+            edge.addLabel(extraLabels[0], Arrays.copyOfRange(extraLabels, 1, extraLabels.length));
+        }
 
         // trigger callbacks for eventing - in this case, it's a VertexAddedEvent
         EventUtil.registerEdgeCreationWithGenericEventRegistry(callbackRegistry, getTraversal(), edge);
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PropertyMapStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PropertyMapStep.java
index 25bc143bc3..665ea10e4b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PropertyMapStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PropertyMapStep.java
@@ -25,7 +25,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.Configuring;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.WithOptions;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.OptionsStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalProduct;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
@@ -220,10 +219,7 @@ public class PropertyMapStep<K,E> extends ScalarMapStep<Element, Map<K, E>>
      * or source-level {@code g.with("multilabel")}.
      */
     private boolean isMultilabelEnabled() {
-        if (this.multilabel) return true;
-        return getTraversal().getStrategies().getStrategy(OptionsStrategy.class)
-                .map(os -> os.getOptions().containsKey("multilabel") || os.getOptions().containsKey(WithOptions.multilabel))
-                .orElse(false);
+        return WithOptions.isMultilabelEnabled(this.multilabel, getTraversal());
     }
 
     protected Object getElementId(Element element){
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AddLabelStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AddLabelStep.java
index c239623601..1cb2d01108 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AddLabelStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AddLabelStep.java
@@ -26,7 +26,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.CallbackRe
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.EventUtil;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.ListCallbackRegistry;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.EventStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
 import org.apache.tinkerpop.gremlin.structure.Element;
@@ -36,9 +35,9 @@ import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Objects;
-import java.util.Optional;
 import java.util.Set;
 
 /**
@@ -48,11 +47,11 @@ import java.util.Set;
  * @since 4.0.0
  */
 public class AddLabelStep<S extends Element> extends SideEffectStep<S>
-        implements Mutating<Event.ElementPropertyChangedEvent>, TraversalParent {
+        implements Mutating<Event.ElementLabelChangedEvent>, TraversalParent {
 
     private final String[] labels;
     private Traversal.Admin<S, String> labelTraversal;
-    private CallbackRegistry<Event.ElementPropertyChangedEvent> callbackRegistry;
+    private CallbackRegistry<Event.ElementLabelChangedEvent> callbackRegistry;
 
     public AddLabelStep(final Traversal.Admin traversal, final String label, final String... moreLabels) {
         super(traversal);
@@ -76,6 +75,7 @@ public class AddLabelStep<S extends Element> extends SideEffectStep<S>
     @Override
     protected void sideEffect(final Traverser.Admin<S> traverser) {
         final Element element = traverser.get();
+        final Set<String> oldLabels = new LinkedHashSet<>(element.labels());
 
         if (this.labelTraversal != null) {
             final List<String> collectedLabels = new ArrayList<>();
@@ -93,16 +93,14 @@ public class AddLabelStep<S extends Element> extends SideEffectStep<S>
                     Arrays.copyOfRange(this.labels, 1, this.labels.length));
         }
 
-        // trigger event callbacks
-        final Optional<EventStrategy> optEventStrategy = getTraversal().getStrategies().getStrategy(EventStrategy.class);
-        if (EventUtil.hasAnyCallbacks(callbackRegistry) && optEventStrategy.isPresent()) {
-            final EventStrategy es = optEventStrategy.get();
-            EventUtil.registerPropertyChange(callbackRegistry, es, element, null, null, new Object[0]);
+        // trigger event callbacks only if labels actually changed
+        if (!oldLabels.equals(element.labels())) {
+            EventUtil.registerLabelChange(callbackRegistry, getTraversal(), element, oldLabels, element.labels());
         }
     }
 
     @Override
-    public CallbackRegistry<Event.ElementPropertyChangedEvent> getMutatingCallbackRegistry() {
+    public CallbackRegistry<Event.ElementLabelChangedEvent> getMutatingCallbackRegistry() {
         if (null == callbackRegistry) callbackRegistry = new ListCallbackRegistry<>();
         return callbackRegistry;
     }
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/DropLabelsStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/DropLabelsStep.java
index 14e5d0634f..9812b0b786 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/DropLabelsStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/DropLabelsStep.java
@@ -26,7 +26,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.CallbackRe
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.EventUtil;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.ListCallbackRegistry;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.EventStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
 import org.apache.tinkerpop.gremlin.structure.Element;
@@ -35,8 +34,8 @@ import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.LinkedHashSet;
 import java.util.List;
-import java.util.Optional;
 import java.util.Set;
 
 /**
@@ -46,12 +45,12 @@ import java.util.Set;
  * @since 4.0.0
  */
 public class DropLabelsStep<S extends Element> extends SideEffectStep<S>
-        implements Mutating<Event.ElementPropertyChangedEvent>, TraversalParent {
+        implements Mutating<Event.ElementLabelChangedEvent>, TraversalParent {
 
     private final boolean dropAll;
     private final String[] labels;
     private Traversal.Admin<S, String> labelTraversal;
-    private CallbackRegistry<Event.ElementPropertyChangedEvent> callbackRegistry;
+    private CallbackRegistry<Event.ElementLabelChangedEvent> callbackRegistry;
 
     /**
      * Constructor for dropLabels() - removes all labels.
@@ -89,6 +88,7 @@ public class DropLabelsStep<S extends Element> extends SideEffectStep<S>
     @Override
     protected void sideEffect(final Traverser.Admin<S> traverser) {
         final Element element = traverser.get();
+        final Set<String> oldLabels = new LinkedHashSet<>(element.labels());
 
         if (this.labelTraversal != null) {
             final String label = TraversalUtil.apply(traverser, this.labelTraversal);
@@ -102,16 +102,14 @@ public class DropLabelsStep<S extends Element> extends SideEffectStep<S>
                     Arrays.copyOfRange(this.labels, 1, this.labels.length));
         }
 
-        // trigger event callbacks
-        final Optional<EventStrategy> optEventStrategy = getTraversal().getStrategies().getStrategy(EventStrategy.class);
-        if (EventUtil.hasAnyCallbacks(callbackRegistry) && optEventStrategy.isPresent()) {
-            final EventStrategy es = optEventStrategy.get();
-            EventUtil.registerPropertyChange(callbackRegistry, es, element, null, null, new Object[0]);
+        // trigger event callbacks only if labels actually changed
+        if (!oldLabels.equals(element.labels())) {
+            EventUtil.registerLabelChange(callbackRegistry, getTraversal(), element, oldLabels, element.labels());
         }
     }
 
     @Override
-    public CallbackRegistry<Event.ElementPropertyChangedEvent> getMutatingCallbackRegistry() {
+    public CallbackRegistry<Event.ElementLabelChangedEvent> getMutatingCallbackRegistry() {
         if (null == callbackRegistry) callbackRegistry = new ListCallbackRegistry<>();
         return callbackRegistry;
     }
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/WithOptions.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/WithOptions.java
index d9101feb97..dd139ca7ba 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/WithOptions.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/WithOptions.java
@@ -18,8 +18,10 @@
  */
 package org.apache.tinkerpop.gremlin.process.traversal.step.util;
 
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.IndexStep;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.OptionsStrategy;
 import org.apache.tinkerpop.gremlin.structure.Edge;
 import org.apache.tinkerpop.gremlin.structure.Element;
 import org.apache.tinkerpop.gremlin.structure.Graph;
@@ -112,4 +114,20 @@ public class WithOptions {
      * @since 4.0.0
      */
     public static final String multilabel = Graph.Hidden.hide("tinkerpop.multilabel");
+
+    /**
+     * The user-facing key for multilabel configuration used with {@code g.with("multilabel")}.
+     */
+    public static final String MULTILABEL_KEY = "multilabel";
+
+    /**
+     * Checks whether multi-label output is enabled for the given traversal, either at the step level
+     * (via step-level configuration) or at the source level (via {@code g.with("multilabel")}).
+     */
+    public static boolean isMultilabelEnabled(final boolean stepLevelEnabled, final Traversal.Admin<?, ?> traversal) {
+        if (stepLevelEnabled) return true;
+        return traversal.getStrategies().getStrategy(OptionsStrategy.class)
+                .map(os -> os.getOptions().containsKey(MULTILABEL_KEY) || os.getOptions().containsKey(multilabel))
+                .orElse(false);
+    }
 }
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/Event.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/Event.java
index 4a9d9c06e6..f02e6bc63f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/Event.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/Event.java
@@ -27,6 +27,7 @@ import org.apache.tinkerpop.gremlin.structure.Vertex;
 import org.apache.tinkerpop.gremlin.structure.VertexProperty;
 
 import java.util.Iterator;
+import java.util.Set;
 
 /**
  * A representation of some action that occurs on a {@link Graph} for a {@link Traversal}.
@@ -213,6 +214,31 @@ public interface Event {
         }
     }
 
+    /**
+     * An event that represents a label change on an element (vertex or edge).
+     * Fired when labels are added or removed via addLabel()/dropLabel()/dropLabels() steps.
+     */
+    class ElementLabelChangedEvent implements Event {
+        private final Element element;
+        private final Set<String> oldLabels;
+        private final Set<String> newLabels;
+
+        public ElementLabelChangedEvent(final Element element, final Set<String> oldLabels, final Set<String> newLabels) {
+            this.element = element;
+            this.oldLabels = oldLabels;
+            this.newLabels = newLabels;
+        }
+
+        public Element getElement() { return element; }
+        public Set<String> getOldLabels() { return oldLabels; }
+        public Set<String> getNewLabels() { return newLabels; }
+
+        @Override
+        public void fireEvent(final Iterator<MutationListener> eventListeners) {
+            // Label change events are dispatched directly via CallbackRegistry, not MutationListener.
+        }
+    }
+
     /**
      * A base class for {@link Property} mutation events.
      */
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/EventUtil.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/EventUtil.java
index 2fce97e150..85d8072f89 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/EventUtil.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/event/EventUtil.java
@@ -27,6 +27,8 @@ import org.apache.tinkerpop.gremlin.structure.Property;
 import org.apache.tinkerpop.gremlin.structure.Vertex;
 import org.apache.tinkerpop.gremlin.structure.VertexProperty;
 
+import java.util.Set;
+
 /**
  * Logic for registering events with the {@link EventStrategy} and the callback registry. Extracting this logic allows
  * providers to reuse these utilities more readily.
@@ -202,6 +204,24 @@ public final class EventUtil {
         }
     }
 
+    /**
+     * Register a label change event with the callback registry.
+     */
+    @SuppressWarnings("unchecked")
+    public static void registerLabelChange(final CallbackRegistry<Event.ElementLabelChangedEvent> callbackRegistry,
+                                           final Traversal.Admin<?, ?> traversal, final Element element,
+                                           final Set<String> oldLabels, final Set<String> newLabels) {
+        if (hasAnyCallbacks(callbackRegistry)) {
+            final EventStrategy eventStrategy = ((Traversal.Admin<Object, Object>) traversal)
+                    .getStrategies().getStrategy(EventStrategy.class).orElse(null);
+            final Element detachedElement = eventStrategy != null ? eventStrategy.detach(element) : element;
+            final Event.ElementLabelChangedEvent event = new Event.ElementLabelChangedEvent(detachedElement, oldLabels, newLabels);
+            for (EventCallback<Event.ElementLabelChangedEvent> c : callbackRegistry.getCallbacks()) {
+                c.accept(event);
+            }
+        }
+    }
+
     /**
      * Register a vertex property addition event with the callback registry.
      */
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/EdgeSerializer.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/EdgeSerializer.java
index 6d614d5126..fe48d6f6ae 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/EdgeSerializer.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/binary/types/EdgeSerializer.java
@@ -30,8 +30,11 @@ import org.apache.tinkerpop.gremlin.structure.util.detached.DetachedVertex;
 import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceEdge;
 
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.Collections;
+import java.util.LinkedHashSet;
 import java.util.List;
+import java.util.Set;
 
 /**
  * @author Stephen Mallette (http://stephen.genoprime.com)
@@ -44,25 +47,43 @@ public class EdgeSerializer extends SimpleTypeSerializer<Edge> {
     @Override
     protected Edge readValue(final Buffer buffer, final GraphBinaryReader context) throws IOException {
         final Object id = context.read(buffer);
-        // reading single string value for now according to GraphBinaryV4
-        final String label = (String) context.readValue(buffer, List.class, false).get(0);
+        // Read all labels as List<String> for multi-label support
+        final List<String> labelList = context.readValue(buffer, List.class, false);
 
         final Object inVId = context.read(buffer);
-        // reading single string value for now according to GraphBinaryV4
-        final String inVLabel = (String) context.readValue(buffer, List.class, false).get(0);
+        // Read all inVertex labels as List<String> for multi-label support
+        final List<String> inVLabelList = context.readValue(buffer, List.class, false);
         final Object outVId = context.read(buffer);
-        // reading single string value for now according to GraphBinaryV4
-        final String outVLabel = (String) context.readValue(buffer, List.class, false).get(0);
+        // Read all outVertex labels as List<String> for multi-label support
+        final List<String> outVLabelList = context.readValue(buffer, List.class, false);
 
         // discard the parent vertex
         context.read(buffer);
 
         final List<Property> properties = context.read(buffer);
 
-        final DetachedVertex inV = DetachedVertex.build().setId(inVId).setLabel(inVLabel).create();
-        final DetachedVertex outV = DetachedVertex.build().setId(outVId).setLabel(outVLabel).create();
+        final DetachedVertex.Builder inVBuilder = DetachedVertex.build().setId(inVId);
+        if (inVLabelList.size() == 1) {
+            inVBuilder.setLabel(inVLabelList.get(0));
+        } else if (!inVLabelList.isEmpty()) {
+            inVBuilder.setLabels(new LinkedHashSet<>(inVLabelList));
+        }
+        final DetachedVertex inV = inVBuilder.create();
+
+        final DetachedVertex.Builder outVBuilder = DetachedVertex.build().setId(outVId);
+        if (outVLabelList.size() == 1) {
+            outVBuilder.setLabel(outVLabelList.get(0));
+        } else if (!outVLabelList.isEmpty()) {
+            outVBuilder.setLabels(new LinkedHashSet<>(outVLabelList));
+        }
+        final DetachedVertex outV = outVBuilder.create();
 
-        final DetachedEdge.Builder builder = DetachedEdge.build().setId(id).setLabel(label).setInV(inV).setOutV(outV);
+        final DetachedEdge.Builder builder = DetachedEdge.build().setId(id).setInV(inV).setOutV(outV);
+        if (labelList.size() == 1) {
+            builder.setLabel(labelList.get(0));
+        } else if (!labelList.isEmpty()) {
+            builder.setLabels(new LinkedHashSet<>(labelList));
+        }
 
         if (properties != null) {
             for (final Property p : properties) {
@@ -77,16 +98,28 @@ public class EdgeSerializer extends SimpleTypeSerializer<Edge> {
     protected void writeValue(final Edge value, final Buffer buffer, final GraphBinaryWriter context) throws IOException {
 
         context.write(value.id(), buffer);
-        // wrapping label into list here for now according to GraphBinaryV4, but we aren't allowing null label yet
-        if (value.label() == null) {
-            throw new IOException("Unexpected null value when nullable is false");
+        // Write all edge labels as List<String> for multi-label support
+        final Set<String> edgeLabels = value.labels();
+        if (edgeLabels == null || edgeLabels.isEmpty()) {
+            throw new IOException("Unexpected null or empty labels when nullable is false");
         }
-        context.writeValue(Collections.singletonList(value.label()), buffer, false);
+        context.writeValue(new ArrayList<>(edgeLabels), buffer, false);
 
         context.write(value.inVertex().id(), buffer);
-        context.writeValue(Collections.singletonList(value.inVertex().label()), buffer, false);
+        // Write all inVertex labels as List<String> for multi-label support
+        final Set<String> inVLabels = value.inVertex().labels();
+        if (inVLabels == null || inVLabels.isEmpty()) {
+            throw new IOException("Unexpected null or empty labels when nullable is false");
+        }
+        context.writeValue(new ArrayList<>(inVLabels), buffer, false);
+
         context.write(value.outVertex().id(), buffer);
-        context.writeValue(Collections.singletonList(value.outVertex().label()), buffer, false);
+        // Write all outVertex labels as List<String> for multi-label support
+        final Set<String> outVLabels = value.outVertex().labels();
+        if (outVLabels == null || outVLabels.isEmpty()) {
+            throw new IOException("Unexpected null or empty labels when nullable is false");
+        }
+        context.writeValue(new ArrayList<>(outVLabels), buffer, false);
 
         // we don't serialize the parent Vertex for edges.
         context.write(null, buffer);
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
index 3fd6815077..cad3bb5276 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONSerializersV4.java
@@ -146,7 +146,7 @@ class GraphSONSerializersV4 {
             jsonGenerator.writeStartObject();
 
             jsonGenerator.writeObjectField(GraphSONTokens.ID, edge.id());
-            writeLabel(jsonGenerator, GraphSONTokens.LABEL, edge.label());
+            writeLabels(jsonGenerator, GraphSONTokens.LABEL, edge.labels());
             writeTypeForGraphObjectIfUntyped(jsonGenerator, typeInfo, GraphSONTokens.EDGE);
             writeVertex(GraphSONTokens.IN, edge.inVertex(), jsonGenerator);
             writeVertex(GraphSONTokens.OUT, edge.outVertex(), jsonGenerator);
@@ -160,7 +160,7 @@ class GraphSONSerializersV4 {
             jsonGenerator.writeFieldName(vertexDirection);
             jsonGenerator.writeStartObject();
             jsonGenerator.writeObjectField(GraphSONTokens.ID, v.id());
-            writeLabel(jsonGenerator, GraphSONTokens.LABEL, v.label());
+            writeLabels(jsonGenerator, GraphSONTokens.LABEL, v.labels());
             jsonGenerator.writeEndObject();
         }
 
@@ -438,8 +438,14 @@ class GraphSONSerializersV4 {
                     e.setId(deserializationContext.readValue(jsonParser, Object.class));
                 } else if (jsonParser.getCurrentName().equals(GraphSONTokens.LABEL)) {
                     jsonParser.nextToken();
+                    final java.util.Set<String> labels = new java.util.LinkedHashSet<>();
                     while (jsonParser.nextToken() != JsonToken.END_ARRAY) {
-                        e.setLabel(jsonParser.getText());
+                        labels.add(jsonParser.getText());
+                    }
+                    if (labels.size() == 1) {
+                        e.setLabel(labels.iterator().next());
+                    } else if (!labels.isEmpty()) {
+                        e.setLabels(labels);
                     }
                 } else if (jsonParser.getCurrentName().equals(GraphSONTokens.OUT)) {
                     jsonParser.nextToken();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedEdge.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedEdge.java
index 2c91afb615..77f53876d4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedEdge.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/detached/DetachedEdge.java
@@ -30,8 +30,10 @@ import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 /**
  * Represents an {@link Edge} that is disconnected from a {@link Graph}.  "Disconnection" can mean detachment from
@@ -51,6 +53,7 @@ public class DetachedEdge extends DetachedElement<Edge> implements Edge {
 
     private DetachedVertex outVertex;
     private DetachedVertex inVertex;
+    private Set<String> edgeLabels;
 
     private DetachedEdge() {}
 
@@ -59,6 +62,12 @@ public class DetachedEdge extends DetachedElement<Edge> implements Edge {
         this.outVertex = DetachedFactory.detach(edge.outVertex(), false);
         this.inVertex = DetachedFactory.detach(edge.inVertex(), false);
 
+        // Capture all labels from the source edge for multi-label support.
+        final Set<String> srcLabels = edge.labels();
+        if (srcLabels.size() > 1) {
+            this.edgeLabels = new LinkedHashSet<>(srcLabels);
+        }
+
         // only serialize properties if requested, the graph supports it and there are meta properties present.
         // this prevents unnecessary object creation of a new HashMap of a new HashMap which will just be empty.
         // it will use Collections.emptyMap() by default
@@ -113,6 +122,23 @@ public class DetachedEdge extends DetachedElement<Edge> implements Edge {
         return StringFactory.edgeString(this);
     }
 
+    @Override
+    public Set<String> labels() {
+        if (this.edgeLabels != null) {
+            return Collections.unmodifiableSet(this.edgeLabels);
+        }
+        // Fall back to single label from parent
+        return this.label != null ? Collections.singleton(this.label) : Collections.emptySet();
+    }
+
+    @Override
+    public String label() {
+        if (this.edgeLabels != null && !this.edgeLabels.isEmpty()) {
+            return this.edgeLabels.iterator().next();
+        }
+        return this.label != null ? this.label : Edge.DEFAULT_LABEL;
+    }
+
     @Override
     public Vertex inVertex() {
         return this.inVertex;
@@ -180,6 +206,14 @@ public class DetachedEdge extends DetachedElement<Edge> implements Edge {
             return this;
         }
 
+        public Builder setLabels(final Set<String> labels) {
+            e.edgeLabels = labels != null ? new LinkedHashSet<>(labels) : null;
+            if (labels != null && !labels.isEmpty()) {
+                e.label = labels.iterator().next();
+            }
+            return this;
+        }
+
         public Builder setOutV(final DetachedVertex v) {
             e.outVertex = v;
             return this;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceEdge.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceEdge.java
index 6f716022ef..8f797b96b3 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceEdge.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferenceEdge.java
@@ -28,6 +28,8 @@ import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.util.Collections;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.Set;
 
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -36,6 +38,7 @@ public class ReferenceEdge extends ReferenceElement<Edge> implements Edge {
 
     private ReferenceVertex inVertex;
     private ReferenceVertex outVertex;
+    private Set<String> edgeLabels;
 
     private ReferenceEdge() {
 
@@ -45,6 +48,11 @@ public class ReferenceEdge extends ReferenceElement<Edge> implements Edge {
         super(edge);
         this.inVertex = new ReferenceVertex(edge.inVertex());
         this.outVertex = new ReferenceVertex(edge.outVertex());
+        // Capture all labels from the source edge for multi-label support.
+        final Set<String> srcLabels = edge.labels();
+        if (srcLabels.size() > 1) {
+            this.edgeLabels = new LinkedHashSet<>(srcLabels);
+        }
     }
 
     public ReferenceEdge(final Object id, final String label, final ReferenceVertex inVertex, final ReferenceVertex outVertex) {
@@ -53,6 +61,29 @@ public class ReferenceEdge extends ReferenceElement<Edge> implements Edge {
         this.outVertex = outVertex;
     }
 
+    public ReferenceEdge(final Object id, final Set<String> labels, final ReferenceVertex inVertex, final ReferenceVertex outVertex) {
+        super(id, labels != null && !labels.isEmpty() ? labels.iterator().next() : Edge.DEFAULT_LABEL);
+        this.edgeLabels = labels != null ? new LinkedHashSet<>(labels) : null;
+        this.inVertex = inVertex;
+        this.outVertex = outVertex;
+    }
+
+    @Override
+    public Set<String> labels() {
+        if (this.edgeLabels != null) {
+            return Collections.unmodifiableSet(this.edgeLabels);
+        }
+        return this.label != null ? Collections.singleton(this.label) : Collections.emptySet();
+    }
+
+    @Override
+    public String label() {
+        if (this.edgeLabels != null && !this.edgeLabels.isEmpty()) {
+            return this.edgeLabels.iterator().next();
+        }
+        return this.label != null ? this.label : Edge.DEFAULT_LABEL;
+    }
+
     @Override
     public <V> Property<V> property(final String key, final V value) {
         throw Element.Exceptions.propertyAdditionNotSupported();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/star/StarGraph.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/star/StarGraph.java
index 8daaf64aef..1981a3257b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/star/StarGraph.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/star/StarGraph.java
@@ -43,6 +43,7 @@ import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
@@ -206,6 +207,12 @@ public final class StarGraph implements Graph, Serializable {
         final StarGraph starGraph = new StarGraph();
         final StarVertex starVertex = (StarVertex) starGraph.addVertex(T.id, vertex.id(), T.label, vertex.label());
 
+        // Copy multi-labels from source vertex
+        final Set<String> srcLabels = vertex.labels();
+        if (srcLabels.size() > 1) {
+            starVertex.setLabels(srcLabels);
+        }
+
         final boolean supportsMetaProperties = vertex.graph().features().vertex().supportsMetaProperties();
 
         vertex.properties().forEachRemaining(vp -> {
@@ -216,11 +223,19 @@ public final class StarGraph implements Graph, Serializable {
         vertex.edges(Direction.IN).forEachRemaining(edge -> {
             final Edge starEdge = starVertex.addInEdge(edge.label(), starGraph.addVertex(T.id, edge.outVertex().id()), T.id, edge.id());
             edge.properties().forEachRemaining(p -> starEdge.property(p.key(), p.value()));
+            final Set<String> edgeSrcLabels = edge.labels();
+            if (edgeSrcLabels.size() > 1) {
+                ((StarGraph.StarEdge) starEdge).setLabels(edgeSrcLabels);
+            }
         });
 
         vertex.edges(Direction.OUT).forEachRemaining(edge -> {
             final Edge starEdge = starVertex.addOutEdge(edge.label(), starGraph.addVertex(T.id, edge.inVertex().id()), T.id, edge.id());
             edge.properties().forEachRemaining(p -> starEdge.property(p.key(), p.value()));
+            final Set<String> edgeSrcLabels = edge.labels();
+            if (edgeSrcLabels.size() > 1) {
+                ((StarGraph.StarEdge) starEdge).setLabels(edgeSrcLabels);
+            }
         });
         return starGraph;
     }
@@ -308,7 +323,7 @@ public final class StarGraph implements Graph, Serializable {
     public abstract class StarElement<E extends Element> implements Element, Attachable<E> {
 
         protected final Object id;
-        protected final String label;
+        protected String label;
 
         protected StarElement(final Object id, final String label) {
             this.id = id;
@@ -352,12 +367,35 @@ public final class StarGraph implements Graph, Serializable {
 
     public final class StarVertex extends StarElement<Vertex> implements Vertex {
 
+        private Set<String> vertexLabels;
         protected Map<String, List<Edge>> outEdges = null;
         protected Map<String, List<Edge>> inEdges = null;
         protected Map<String, List<VertexProperty>> vertexProperties = null;
 
         public StarVertex(final Object id, final String label) {
             super(id, label);
+            this.vertexLabels = new LinkedHashSet<>();
+            this.vertexLabels.add(internStrings ? label.intern() : label);
+        }
+
+        @Override
+        public Set<String> labels() {
+            return Collections.unmodifiableSet(this.vertexLabels);
+        }
+
+        @Override
+        public String label() {
+            return this.vertexLabels.isEmpty() ? this.label : this.vertexLabels.iterator().next();
+        }
+
+        /**
+         * Sets the vertex labels from a source set. Used when copying labels from a multi-label vertex.
+         */
+        public void setLabels(final Set<String> labels) {
+            if (labels != null && !labels.isEmpty()) {
+                this.vertexLabels = new LinkedHashSet<>(labels);
+                this.label = this.vertexLabels.iterator().next();
+            }
         }
 
         private void dropEdgeProperty(Object id) {
@@ -774,11 +812,34 @@ public final class StarGraph implements Graph, Serializable {
 
     public abstract class StarEdge extends StarElement<Edge> implements Edge {
 
+        private Set<String> edgeLabels;
         protected final Object otherId;
 
         private StarEdge(final Object id, final String label, final Object otherId) {
             super(id, label);
             this.otherId = otherId;
+            this.edgeLabels = new LinkedHashSet<>();
+            this.edgeLabels.add(internStrings ? label.intern() : label);
+        }
+
+        @Override
+        public Set<String> labels() {
+            return Collections.unmodifiableSet(this.edgeLabels);
+        }
+
+        @Override
+        public String label() {
+            return this.edgeLabels.isEmpty() ? this.label : this.edgeLabels.iterator().next();
+        }
+
+        /**
+         * Sets the edge labels from a source set. Used when copying labels from a multi-label edge.
+         */
+        public void setLabels(final Set<String> labels) {
+            if (labels != null && !labels.isEmpty()) {
+                this.edgeLabels = new LinkedHashSet<>(labels);
+                this.label = this.edgeLabels.iterator().next();
+            }
         }
 
         @Override
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
index 6aee902762..04969b5fae 100644
--- a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
@@ -125,6 +125,12 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
                         continue;
                     }
 
+                    if (scenario.Tags.Any(t => t.Name == "@MultiLabel"))
+                    {
+                        failedSteps.Add(scenario.Steps.First(), new IgnoreException(IgnoreReason.MultiLabelStepsNotSupported));
+                        continue;
+                    }
+
                     StepBlock? currentStep = null;
                     StepDefinition? stepDefinition = null;
                     foreach (var step in scenario.Steps)
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
index 7001391004..bf3918f253 100644
--- a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
@@ -70,6 +70,11 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
         /// <summary>
         /// write() is not supported yet for testing
         /// </summary>
-        WriteStepTestingNotSupported
+        WriteStepTestingNotSupported,
+
+        /// <summary>
+        /// Multi-label steps (labels(), addLabel(), dropLabel(), dropLabels()) are not yet available in the .NET GLV
+        /// </summary>
+        MultiLabelStepsNotSupported
     }
 }
\ No newline at end of file
diff --git a/gremlin-go/driver/cucumber/cucumberSteps_test.go b/gremlin-go/driver/cucumber/cucumberSteps_test.go
index 149bc9bc07..fd69c063d0 100644
--- a/gremlin-go/driver/cucumber/cucumberSteps_test.go
+++ b/gremlin-go/driver/cucumber/cucumberSteps_test.go
@@ -1130,6 +1130,7 @@ func TestCucumberFeatures(t *testing.T) {
 		ScenarioInitializer:  InitializeScenario,
 		Options: &godog.Options{
 			Tags:     "~@GraphComputerOnly && ~@AllowNullPropertyValues && ~@StepTree && ~@StepWrite && ~@DataChar",
+			Tags:     "~@GraphComputerOnly && ~@AllowNullPropertyValues && ~@StepTree && ~@StepWrite && ~@DataChar && ~@MultiLabel",
 			Format:   "pretty",
 			Paths:    []string{getEnvOrDefaultString("CUCUMBER_FEATURE_FOLDER", "../../../gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features")},
 			TestingT: t, // Testing instance that will run subtests.
diff --git a/gremlin-js/gremlin-javascript/test/cucumber/world.js b/gremlin-js/gremlin-javascript/test/cucumber/world.js
index 563abb8ce8..8dcd7d18ba 100644
--- a/gremlin-js/gremlin-javascript/test/cucumber/world.js
+++ b/gremlin-js/gremlin-javascript/test/cucumber/world.js
@@ -118,6 +118,10 @@ Before({tags: "@DataDuration"}, function() {
   return 'skipped'
 })
 
+Before({tags: "@MultiLabel"}, function() {
+  return 'skipped'
+})
+
 function getVertices(connection) {
   const g = anon.traversal().withRemote(connection);
   return g.V().group().by('name').by(__.tail()).next().then(it => {
diff --git a/gremlin-language/src/main/antlr4/Gremlin.g4 b/gremlin-language/src/main/antlr4/Gremlin.g4
index f10489dd1b..3392483b08 100644
--- a/gremlin-language/src/main/antlr4/Gremlin.g4
+++ b/gremlin-language/src/main/antlr4/Gremlin.g4
@@ -112,7 +112,9 @@ traversalSourceSpawnMethod
     ;
 
 traversalSourceSpawnMethod_addE
-    : K_ADDE LPAREN stringArgument RPAREN
+    : K_ADDE LPAREN RPAREN
+    | K_ADDE LPAREN stringArgument RPAREN
+    | K_ADDE LPAREN stringArgument COMMA stringArgument (COMMA stringArgument)* RPAREN
     | K_ADDE LPAREN nestedTraversal RPAREN
     ;
 
@@ -331,7 +333,9 @@ traversalMethod_E
     ;
 
 traversalMethod_addE
-    : K_ADDE LPAREN stringArgument RPAREN #traversalMethod_addE_String
+    : K_ADDE LPAREN RPAREN #traversalMethod_addE_Empty
+    | K_ADDE LPAREN stringArgument RPAREN #traversalMethod_addE_String
+    | K_ADDE LPAREN stringArgument (COMMA stringArgument)+ RPAREN #traversalMethod_addE_StringVarargs
     | K_ADDE LPAREN nestedTraversal RPAREN #traversalMethod_addE_Traversal
     ;
 
diff --git a/gremlin-python/src/main/python/tests/feature/feature_steps.py b/gremlin-python/src/main/python/tests/feature/feature_steps.py
index f40c3fa91e..56feab3a29 100644
--- a/gremlin-python/src/main/python/tests/feature/feature_steps.py
+++ b/gremlin-python/src/main/python/tests/feature/feature_steps.py
@@ -90,6 +90,10 @@ def choose_graph(step, graph_name):
     if not step.context.ignore:
         step.context.ignore = "WithReservedKeysVerificationStrategy" in tagset
 
+    # Multi-label steps not yet available in Python GLV
+    if not step.context.ignore:
+        step.context.ignore = "MultiLabel" in tagset
+
     if (step.context.ignore):
         return
 
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
index f152691348..aaf373e313 100644
--- a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
@@ -19290,6 +19290,76 @@
             }
         ]
     },
+    {
+        "scenario": "g_addVXa_bX_labels",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\").labels().fold()",
+                "language": "g.addV(\"a\", \"b\").labels().fold()",
+                "canonical": "g.addV(\"a\", \"b\").labels().fold()",
+                "anonymized": "g.addV(string0, string1).labels().fold()",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\").Labels().Fold()",
+                "go": "g.AddV(\"a\", \"b\").Labels().Fold()",
+                "groovy": "g.addV(\"a\", \"b\").labels().fold()",
+                "java": "g.addV(\"a\", \"b\").labels().fold()",
+                "javascript": "g.addV(\"a\", \"b\").labels().fold()",
+                "python": "g.add_v('a', 'b').labels().fold()"
+            },
+            {
+                "original": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "language": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "canonical": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1)",
+                "dotnet": "g.V().HasLabel(\"a\").HasLabel(\"b\")",
+                "go": "g.V().HasLabel(\"a\").HasLabel(\"b\")",
+                "groovy": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "java": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "javascript": "g.V().hasLabel(\"a\").hasLabel(\"b\")",
+                "python": "g.V().has_label('a').has_label('b')"
+            },
+            {
+                "original": "g.addV(\"a\", \"b\")",
+                "language": "g.addV(\"a\", \"b\")",
+                "canonical": "g.addV(\"a\", \"b\")",
+                "anonymized": "g.addV(string0, string1)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\")",
+                "go": "g.AddV(\"a\", \"b\")",
+                "groovy": "g.addV(\"a\", \"b\")",
+                "java": "g.addV(\"a\", \"b\")",
+                "javascript": "g.addV(\"a\", \"b\")",
+                "python": "g.add_v('a', 'b')"
+            },
+            {
+                "original": "g.V().labels()",
+                "language": "g.V().labels()",
+                "canonical": "g.V().labels()",
+                "anonymized": "g.V().labels()",
+                "dotnet": "g.V().Labels()",
+                "go": "g.V().Labels()",
+                "groovy": "g.V().labels()",
+                "java": "g.V().labels()",
+                "javascript": "g.V().labels()",
+                "python": "g.V().labels()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_addVXa_b_cX_labels_count",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "language": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "canonical": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "anonymized": "g.addV(string0, string1, string2).labels().count()",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\", (string) \"c\").Labels().Count()",
+                "go": "g.AddV(\"a\", \"b\", \"c\").Labels().Count()",
+                "groovy": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "java": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "javascript": "g.addV(\"a\", \"b\", \"c\").labels().count()",
+                "python": "g.add_v('a', 'b', 'c').labels().count()"
+            }
+        ]
+    },
     {
         "scenario": "g_injectX1X_asBool",
         "traversals": [
@@ -24396,6 +24466,127 @@
             }
         ]
     },
+    {
+        "scenario": "g_V_hasLabelXpersonX_labels",
+        "traversals": [
+            {
+                "original": "g.V().hasLabel(\"person\").labels()",
+                "language": "g.V().hasLabel(\"person\").labels()",
+                "canonical": "g.V().hasLabel(\"person\").labels()",
+                "anonymized": "g.V().hasLabel(string0).labels()",
+                "dotnet": "g.V().HasLabel(\"person\").Labels()",
+                "go": "g.V().HasLabel(\"person\").Labels()",
+                "groovy": "g.V().hasLabel(\"person\").labels()",
+                "java": "g.V().hasLabel(\"person\").labels()",
+                "javascript": "g.V().hasLabel(\"person\").labels()",
+                "python": "g.V().has_label('person').labels()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_addVXa_bX_labels_fold",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\")",
+                "language": "g.addV(\"a\", \"b\")",
+                "canonical": "g.addV(\"a\", \"b\")",
+                "anonymized": "g.addV(string0, string1)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\")",
+                "go": "g.AddV(\"a\", \"b\")",
+                "groovy": "g.addV(\"a\", \"b\")",
+                "java": "g.addV(\"a\", \"b\")",
+                "javascript": "g.addV(\"a\", \"b\")",
+                "python": "g.add_v('a', 'b')"
+            },
+            {
+                "original": "g.V().labels().fold()",
+                "language": "g.V().labels().fold()",
+                "canonical": "g.V().labels().fold()",
+                "anonymized": "g.V().labels().fold()",
+                "dotnet": "g.V().Labels().Fold()",
+                "go": "g.V().Labels().Fold()",
+                "groovy": "g.V().labels().fold()",
+                "java": "g.V().labels().fold()",
+                "javascript": "g.V().labels().fold()",
+                "python": "g.V().labels().fold()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_addVXa_bX_labels_count",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\")",
+                "language": "g.addV(\"a\", \"b\")",
+                "canonical": "g.addV(\"a\", \"b\")",
+                "anonymized": "g.addV(string0, string1)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\")",
+                "go": "g.AddV(\"a\", \"b\")",
+                "groovy": "g.addV(\"a\", \"b\")",
+                "java": "g.addV(\"a\", \"b\")",
+                "javascript": "g.addV(\"a\", \"b\")",
+                "python": "g.add_v('a', 'b')"
+            },
+            {
+                "original": "g.V().labels().count()",
+                "language": "g.V().labels().count()",
+                "canonical": "g.V().labels().count()",
+                "anonymized": "g.V().labels().count()",
+                "dotnet": "g.V().Labels().Count()",
+                "go": "g.V().Labels().Count()",
+                "groovy": "g.V().labels().count()",
+                "java": "g.V().labels().count()",
+                "javascript": "g.V().labels().count()",
+                "python": "g.V().labels().count()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_addV_labels",
+        "traversals": [
+            {
+                "original": "g.addV()",
+                "language": "g.addV()",
+                "canonical": "g.addV()",
+                "anonymized": "g.addV()",
+                "dotnet": "g.AddV()",
+                "go": "g.AddV()",
+                "groovy": "g.addV()",
+                "java": "g.addV()",
+                "javascript": "g.addV()",
+                "python": "g.add_v()"
+            },
+            {
+                "original": "g.V().labels()",
+                "language": "g.V().labels()",
+                "canonical": "g.V().labels()",
+                "anonymized": "g.V().labels()",
+                "dotnet": "g.V().Labels()",
+                "go": "g.V().Labels()",
+                "groovy": "g.V().labels()",
+                "java": "g.V().labels()",
+                "javascript": "g.V().labels()",
+                "python": "g.V().labels()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_E_labels",
+        "traversals": [
+            {
+                "original": "g.E().hasLabel(\"knows\").labels()",
+                "language": "g.E().hasLabel(\"knows\").labels()",
+                "canonical": "g.E().hasLabel(\"knows\").labels()",
+                "anonymized": "g.E().hasLabel(string0).labels()",
+                "dotnet": "g.E().HasLabel(\"knows\").Labels()",
+                "go": "g.E().HasLabel(\"knows\").Labels()",
+                "groovy": "g.E().hasLabel(\"knows\").labels()",
+                "java": "g.E().hasLabel(\"knows\").labels()",
+                "javascript": "g.E().hasLabel(\"knows\").labels()",
+                "python": "g.E().has_label('knows').labels()"
+            }
+        ]
+    },
     {
         "scenario": "g_injectXfeature_test_nullX_length",
         "traversals": [
@@ -32674,6 +32865,454 @@
             }
         ]
     },
+    {
+        "scenario": "g_mergeVXlabel_ab_name_markoX_multilabel_create",
+        "traversals": [
+            {
+                "original": "g.mergeV([(T.label): [\"person\",\"employee\"], name: \"marko\"])",
+                "language": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "canonical": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "anonymized": "g.mergeV(map0)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> { \"person\", \"employee\" } }, { \"name\", \"marko\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: []interface{}{\"person\", \"employee\"}, \"name\": \"marko\" })",
+                "groovy": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{ add(\"person\"); add(\"employee\"); }}); put(\"name\", \"marko\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, [\"person\", \"employee\"]], [\"name\", \"marko\"]]))",
+                "python": "g.merge_v({ T.label: ['person', 'employee'], 'name': 'marko' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "language": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "canonical": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1)",
+                "dotnet": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "go": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "groovy": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "java": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "javascript": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "python": "g.V().has_label('person').has_label('employee')"
+            },
+            {
+                "original": "g.V().has(\"name\",\"marko\")",
+                "language": "g.V().has(\"name\", \"marko\")",
+                "canonical": "g.V().has(\"name\", \"marko\")",
+                "anonymized": "g.V().has(string0, string1)",
+                "dotnet": "g.V().Has(\"name\", \"marko\")",
+                "go": "g.V().Has(\"name\", \"marko\")",
+                "groovy": "g.V().has(\"name\", \"marko\")",
+                "java": "g.V().has(\"name\", \"marko\")",
+                "javascript": "g.V().has(\"name\", \"marko\")",
+                "python": "g.V().has('name', 'marko')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_abc_name_testX_multilabel_create",
+        "traversals": [
+            {
+                "original": "g.mergeV([(T.label): [\"a\",\"b\",\"c\"], name: \"test\"])",
+                "language": "g.mergeV([(T.label):[\"a\", \"b\", \"c\"], name:\"test\"])",
+                "canonical": "g.mergeV([(T.label):[\"a\", \"b\", \"c\"], name:\"test\"])",
+                "anonymized": "g.mergeV(map0)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> { \"a\", \"b\", \"c\" } }, { \"name\", \"test\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: []interface{}{\"a\", \"b\", \"c\"}, \"name\": \"test\" })",
+                "groovy": "g.mergeV([(T.label):[\"a\", \"b\", \"c\"], name:\"test\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{ add(\"a\"); add(\"b\"); add(\"c\"); }}); put(\"name\", \"test\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, [\"a\", \"b\", \"c\"]], [\"name\", \"test\"]]))",
+                "python": "g.merge_v({ T.label: ['a', 'b', 'c'], 'name': 'test' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "language": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "canonical": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1).hasLabel(string2)",
+                "dotnet": "g.V().HasLabel(\"a\").HasLabel(\"b\").HasLabel(\"c\")",
+                "go": "g.V().HasLabel(\"a\").HasLabel(\"b\").HasLabel(\"c\")",
+                "groovy": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "java": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "javascript": "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")",
+                "python": "g.V().has_label('a').has_label('b').has_label('c')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_person_name_markoX_single_label",
+        "traversals": [
+            {
+                "original": "g.mergeV([(T.label): \"person\", name: \"marko\"])",
+                "language": "g.mergeV([(T.label):\"person\", name:\"marko\"])",
+                "canonical": "g.mergeV([(T.label):\"person\", name:\"marko\"])",
+                "anonymized": "g.mergeV(map0)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, \"person\" }, { \"name\", \"marko\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: \"person\", \"name\": \"marko\" })",
+                "groovy": "g.mergeV([(T.label):\"person\", name:\"marko\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, \"person\"); put(\"name\", \"marko\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, \"person\"], [\"name\", \"marko\"]]))",
+                "python": "g.merge_v({ T.label: 'person', 'name': 'marko' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\")",
+                "language": "g.V().hasLabel(\"person\")",
+                "canonical": "g.V().hasLabel(\"person\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"person\")",
+                "go": "g.V().HasLabel(\"person\")",
+                "groovy": "g.V().hasLabel(\"person\")",
+                "java": "g.V().hasLabel(\"person\")",
+                "javascript": "g.V().hasLabel(\"person\")",
+                "python": "g.V().has_label('person')"
+            },
+            {
+                "original": "g.V().has(\"name\",\"marko\")",
+                "language": "g.V().has(\"name\", \"marko\")",
+                "canonical": "g.V().has(\"name\", \"marko\")",
+                "anonymized": "g.V().has(string0, string1)",
+                "dotnet": "g.V().Has(\"name\", \"marko\")",
+                "go": "g.V().Has(\"name\", \"marko\")",
+                "groovy": "g.V().has(\"name\", \"marko\")",
+                "java": "g.V().has(\"name\", \"marko\")",
+                "javascript": "g.V().has(\"name\", \"marko\")",
+                "python": "g.V().has('name', 'marko')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_ab_name_markoX_multilabel_match",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).addLabel(string1).property(string2, string3)",
+                "dotnet": "g.AddV((string) \"person\").AddLabel(\"employee\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").AddLabel(\"employee\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').add_label('employee').property('name', 'marko')"
+            },
+            {
+                "original": "g.mergeV([(T.label): [\"person\",\"employee\"], name: \"marko\"])",
+                "language": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "canonical": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "anonymized": "g.mergeV(map0)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> { \"person\", \"employee\" } }, { \"name\", \"marko\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: []interface{}{\"person\", \"employee\"}, \"name\": \"marko\" })",
+                "groovy": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{ add(\"person\"); add(\"employee\"); }}); put(\"name\", \"marko\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, [\"person\", \"employee\"]], [\"name\", \"marko\"]]))",
+                "python": "g.merge_v({ T.label: ['person', 'employee'], 'name': 'marko' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "language": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "canonical": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1)",
+                "dotnet": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "go": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "groovy": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "java": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "javascript": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "python": "g.V().has_label('person').has_label('employee')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_ab_name_markoX_multilabel_nomatch",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).property(string1, string2)",
+                "dotnet": "g.AddV((string) \"person\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').property('name', 'marko')"
+            },
+            {
+                "original": "g.mergeV([(T.label): [\"person\",\"employee\"], name: \"marko\"])",
+                "language": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "canonical": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "anonymized": "g.mergeV(map0)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> { \"person\", \"employee\" } }, { \"name\", \"marko\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: []interface{}{\"person\", \"employee\"}, \"name\": \"marko\" })",
+                "groovy": "g.mergeV([(T.label):[\"person\", \"employee\"], name:\"marko\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{ add(\"person\"); add(\"employee\"); }}); put(\"name\", \"marko\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, [\"person\", \"employee\"]], [\"name\", \"marko\"]]))",
+                "python": "g.merge_v({ T.label: ['person', 'employee'], 'name': 'marko' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_person_name_markoX_optionXonMatch_label_managerX",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).addLabel(string1).property(string2, string3)",
+                "dotnet": "g.AddV((string) \"person\").AddLabel(\"employee\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").AddLabel(\"employee\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").addLabel(\"employee\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').add_label('employee').property('name', 'marko')"
+            },
+            {
+                "original": "g.mergeV([(T.label): \"person\", name: \"marko\"]).option(Merge.onMatch, [(T.label): \"manager\"])",
+                "language": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):\"manager\"])",
+                "canonical": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):\"manager\"])",
+                "anonymized": "g.mergeV(map0).option(Merge.onMatch, map1)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, \"person\" }, { \"name\", \"marko\" }}).Option(Merge.OnMatch, (IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, \"manager\" }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: \"person\", \"name\": \"marko\" }).Option(gremlingo.Merge.OnMatch, map[interface{}]interface{}{gremlingo.T.Label: \"manager\" })",
+                "groovy": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):\"manager\"])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, \"person\"); put(\"name\", \"marko\"); }}).option(Merge.onMatch, new LinkedHashMap<Object, Object>() {{ put(T.label, \"manager\"); }})",
+                "javascript": "g.mergeV(new Map([[T.label, \"person\"], [\"name\", \"marko\"]])).option(Merge.onMatch, new Map([[T.label, \"manager\"]]))",
+                "python": "g.merge_v({ T.label: 'person', 'name': 'marko' }).option(Merge.on_match, { T.label: 'manager' })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"manager\")",
+                "language": "g.V().hasLabel(\"manager\")",
+                "canonical": "g.V().hasLabel(\"manager\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"manager\")",
+                "go": "g.V().HasLabel(\"manager\")",
+                "groovy": "g.V().hasLabel(\"manager\")",
+                "java": "g.V().hasLabel(\"manager\")",
+                "javascript": "g.V().hasLabel(\"manager\")",
+                "python": "g.V().has_label('manager')"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\")",
+                "language": "g.V().hasLabel(\"person\")",
+                "canonical": "g.V().hasLabel(\"person\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"person\")",
+                "go": "g.V().HasLabel(\"person\")",
+                "groovy": "g.V().hasLabel(\"person\")",
+                "java": "g.V().hasLabel(\"person\")",
+                "javascript": "g.V().hasLabel(\"person\")",
+                "python": "g.V().has_label('person')"
+            },
+            {
+                "original": "g.V().hasLabel(\"employee\")",
+                "language": "g.V().hasLabel(\"employee\")",
+                "canonical": "g.V().hasLabel(\"employee\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"employee\")",
+                "go": "g.V().HasLabel(\"employee\")",
+                "groovy": "g.V().hasLabel(\"employee\")",
+                "java": "g.V().hasLabel(\"employee\")",
+                "javascript": "g.V().hasLabel(\"employee\")",
+                "python": "g.V().has_label('employee')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_person_name_markoX_optionXonMatch_label_manager_directorX",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).property(string1, string2)",
+                "dotnet": "g.AddV((string) \"person\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').property('name', 'marko')"
+            },
+            {
+                "original": "g.mergeV([(T.label): \"person\", name: \"marko\"]).option(Merge.onMatch, [(T.label): [\"manager\",\"director\"]])",
+                "language": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[\"manager\", \"director\"]])",
+                "canonical": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[\"manager\", \"director\"]])",
+                "anonymized": "g.mergeV(map0).option(Merge.onMatch, map1)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, \"person\" }, { \"name\", \"marko\" }}).Option(Merge.OnMatch, (IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> { \"manager\", \"director\" } }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: \"person\", \"name\": \"marko\" }).Option(gremlingo.Merge.OnMatch, map[interface{}]interface{}{gremlingo.T.Label: []interface{}{\"manager\", \"director\"} })",
+                "groovy": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[\"manager\", \"director\"]])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, \"person\"); put(\"name\", \"marko\"); }}).option(Merge.onMatch, new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{ add(\"manager\"); add(\"director\"); }}); }})",
+                "javascript": "g.mergeV(new Map([[T.label, \"person\"], [\"name\", \"marko\"]])).option(Merge.onMatch, new Map([[T.label, [\"manager\", \"director\"]]]))",
+                "python": "g.merge_v({ T.label: 'person', 'name': 'marko' }).option(Merge.on_match, { T.label: ['manager', 'director'] })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "language": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "canonical": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1)",
+                "dotnet": "g.V().HasLabel(\"manager\").HasLabel(\"director\")",
+                "go": "g.V().HasLabel(\"manager\").HasLabel(\"director\")",
+                "groovy": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "java": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "javascript": "g.V().hasLabel(\"manager\").hasLabel(\"director\")",
+                "python": "g.V().has_label('manager').has_label('director')"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\")",
+                "language": "g.V().hasLabel(\"person\")",
+                "canonical": "g.V().hasLabel(\"person\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"person\")",
+                "go": "g.V().HasLabel(\"person\")",
+                "groovy": "g.V().hasLabel(\"person\")",
+                "java": "g.V().hasLabel(\"person\")",
+                "javascript": "g.V().hasLabel(\"person\")",
+                "python": "g.V().has_label('person')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_mergeVXlabel_person_name_markoX_optionXonMatch_label_emptyX",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).property(string1, string2)",
+                "dotnet": "g.AddV((string) \"person\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').property('name', 'marko')"
+            },
+            {
+                "original": "g.mergeV([(T.label): \"person\", name: \"marko\"]).option(Merge.onMatch, [(T.label): []])",
+                "language": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[]])",
+                "canonical": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[]])",
+                "anonymized": "g.mergeV(map0).option(Merge.onMatch, map1)",
+                "dotnet": "g.MergeV((IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, \"person\" }, { \"name\", \"marko\" }}).Option(Merge.OnMatch, (IDictionary<object, object>) new Dictionary<object, object> {{ T.Label, new List<object> {  } }})",
+                "go": "g.MergeV(map[interface{}]interface{}{gremlingo.T.Label: \"person\", \"name\": \"marko\" }).Option(gremlingo.Merge.OnMatch, map[interface{}]interface{}{gremlingo.T.Label: []interface{}{} })",
+                "groovy": "g.mergeV([(T.label):\"person\", name:\"marko\"]).option(Merge.onMatch, [(T.label):[]])",
+                "java": "g.mergeV(new LinkedHashMap<Object, Object>() {{ put(T.label, \"person\"); put(\"name\", \"marko\"); }}).option(Merge.onMatch, new LinkedHashMap<Object, Object>() {{ put(T.label, new ArrayList<Object>() {{  }}); }})",
+                "javascript": "g.mergeV(new Map([[T.label, \"person\"], [\"name\", \"marko\"]])).option(Merge.onMatch, new Map([[T.label, []]]))",
+                "python": "g.merge_v({ T.label: 'person', 'name': 'marko' }).option(Merge.on_match, { T.label: [] })"
+            },
+            {
+                "original": "g.V()",
+                "language": "g.V()",
+                "canonical": "g.V()",
+                "anonymized": "g.V()",
+                "dotnet": "g.V()",
+                "go": "g.V()",
+                "groovy": "g.V()",
+                "java": "g.V()",
+                "javascript": "g.V()",
+                "python": "g.V()"
+            },
+            {
+                "original": "g.V().hasLabel(\"vertex\")",
+                "language": "g.V().hasLabel(\"vertex\")",
+                "canonical": "g.V().hasLabel(\"vertex\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"vertex\")",
+                "go": "g.V().HasLabel(\"vertex\")",
+                "groovy": "g.V().hasLabel(\"vertex\")",
+                "java": "g.V().hasLabel(\"vertex\")",
+                "javascript": "g.V().hasLabel(\"vertex\")",
+                "python": "g.V().has_label('vertex')"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\")",
+                "language": "g.V().hasLabel(\"person\")",
+                "canonical": "g.V().hasLabel(\"person\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"person\")",
+                "go": "g.V().HasLabel(\"person\")",
+                "groovy": "g.V().hasLabel(\"person\")",
+                "java": "g.V().hasLabel(\"person\")",
+                "javascript": "g.V().hasLabel(\"person\")",
+                "python": "g.V().has_label('person')"
+            }
+        ]
+    },
     {
         "scenario": "g_V_age_min",
         "traversals": [
@@ -41231,6 +41870,105 @@
             }
         ]
     },
+    {
+        "scenario": "g_V_hasLabelXpersonX_hasXname_markoX_addLabelXemployeeX_labels",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "language": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "canonical": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "anonymized": "g.addV(string0).property(string1, string2)",
+                "dotnet": "g.AddV((string) \"person\").Property(\"name\", \"marko\")",
+                "go": "g.AddV(\"person\").Property(\"name\", \"marko\")",
+                "groovy": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "java": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "javascript": "g.addV(\"person\").property(\"name\", \"marko\")",
+                "python": "g.add_v('person').property('name', 'marko')"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "language": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "canonical": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "anonymized": "g.V().hasLabel(string0).has(string1, string2).addLabel(string3).labels().fold()",
+                "dotnet": "g.V().HasLabel(\"person\").Has(\"name\", \"marko\").AddLabel(\"employee\").Labels().Fold()",
+                "go": "g.V().HasLabel(\"person\").Has(\"name\", \"marko\").AddLabel(\"employee\").Labels().Fold()",
+                "groovy": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "java": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "javascript": "g.V().hasLabel(\"person\").has(\"name\", \"marko\").addLabel(\"employee\").labels().fold()",
+                "python": "g.V().has_label('person').has('name', 'marko').add_label('employee').labels().fold()"
+            },
+            {
+                "original": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "language": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "canonical": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "anonymized": "g.V().hasLabel(string0).hasLabel(string1)",
+                "dotnet": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "go": "g.V().HasLabel(\"person\").HasLabel(\"employee\")",
+                "groovy": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "java": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "javascript": "g.V().hasLabel(\"person\").hasLabel(\"employee\")",
+                "python": "g.V().has_label('person').has_label('employee')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_V_addLabelXa_bX_labels_count",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\")",
+                "language": "g.addV(\"person\")",
+                "canonical": "g.addV(\"person\")",
+                "anonymized": "g.addV(string0)",
+                "dotnet": "g.AddV((string) \"person\")",
+                "go": "g.AddV(\"person\")",
+                "groovy": "g.addV(\"person\")",
+                "java": "g.addV(\"person\")",
+                "javascript": "g.addV(\"person\")",
+                "python": "g.add_v('person')"
+            },
+            {
+                "original": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "language": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "canonical": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "anonymized": "g.V().addLabel(string0, string1).labels().count()",
+                "dotnet": "g.V().AddLabel(\"a\", \"b\").Labels().Count()",
+                "go": "g.V().AddLabel(\"a\", \"b\").Labels().Count()",
+                "groovy": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "java": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "javascript": "g.V().addLabel(\"a\", \"b\").labels().count()",
+                "python": "g.V().add_label('a', 'b').labels().count()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_V_addLabelXexistingX_labels_count",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\")",
+                "language": "g.addV(\"person\")",
+                "canonical": "g.addV(\"person\")",
+                "anonymized": "g.addV(string0)",
+                "dotnet": "g.AddV((string) \"person\")",
+                "go": "g.AddV(\"person\")",
+                "groovy": "g.addV(\"person\")",
+                "java": "g.addV(\"person\")",
+                "javascript": "g.addV(\"person\")",
+                "python": "g.add_v('person')"
+            },
+            {
+                "original": "g.V().addLabel(\"person\").labels().count()",
+                "language": "g.V().addLabel(\"person\").labels().count()",
+                "canonical": "g.V().addLabel(\"person\").labels().count()",
+                "anonymized": "g.V().addLabel(string0).labels().count()",
+                "dotnet": "g.V().AddLabel(\"person\").Labels().Count()",
+                "go": "g.V().AddLabel(\"person\").Labels().Count()",
+                "groovy": "g.V().addLabel(\"person\").labels().count()",
+                "java": "g.V().addLabel(\"person\").labels().count()",
+                "javascript": "g.V().addLabel(\"person\").labels().count()",
+                "python": "g.V().add_label('person').labels().count()"
+            }
+        ]
+    },
     {
         "scenario": "g_V_valueXnameX_aggregateXxX_capXxX",
         "traversals": [
@@ -42200,6 +42938,146 @@
             }
         ]
     },
+    {
+        "scenario": "g_V_dropLabelXaX_labels",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\")",
+                "language": "g.addV(\"a\", \"b\")",
+                "canonical": "g.addV(\"a\", \"b\")",
+                "anonymized": "g.addV(string0, string1)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\")",
+                "go": "g.AddV(\"a\", \"b\")",
+                "groovy": "g.addV(\"a\", \"b\")",
+                "java": "g.addV(\"a\", \"b\")",
+                "javascript": "g.addV(\"a\", \"b\")",
+                "python": "g.add_v('a', 'b')"
+            },
+            {
+                "original": "g.V().dropLabel(\"a\").labels().fold()",
+                "language": "g.V().dropLabel(\"a\").labels().fold()",
+                "canonical": "g.V().dropLabel(\"a\").labels().fold()",
+                "anonymized": "g.V().dropLabel(string0).labels().fold()",
+                "dotnet": "g.V().DropLabel(\"a\").Labels().Fold()",
+                "go": "g.V().DropLabel(\"a\").Labels().Fold()",
+                "groovy": "g.V().dropLabel(\"a\").labels().fold()",
+                "java": "g.V().dropLabel(\"a\").labels().fold()",
+                "javascript": "g.V().dropLabel(\"a\").labels().fold()",
+                "python": "g.V().drop_label('a').labels().fold()"
+            },
+            {
+                "original": "g.V().hasLabel(\"a\")",
+                "language": "g.V().hasLabel(\"a\")",
+                "canonical": "g.V().hasLabel(\"a\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"a\")",
+                "go": "g.V().HasLabel(\"a\")",
+                "groovy": "g.V().hasLabel(\"a\")",
+                "java": "g.V().hasLabel(\"a\")",
+                "javascript": "g.V().hasLabel(\"a\")",
+                "python": "g.V().has_label('a')"
+            },
+            {
+                "original": "g.V().hasLabel(\"b\")",
+                "language": "g.V().hasLabel(\"b\")",
+                "canonical": "g.V().hasLabel(\"b\")",
+                "anonymized": "g.V().hasLabel(string0)",
+                "dotnet": "g.V().HasLabel(\"b\")",
+                "go": "g.V().HasLabel(\"b\")",
+                "groovy": "g.V().hasLabel(\"b\")",
+                "java": "g.V().hasLabel(\"b\")",
+                "javascript": "g.V().hasLabel(\"b\")",
+                "python": "g.V().has_label('b')"
+            }
+        ]
+    },
+    {
+        "scenario": "g_V_dropLabels_labels",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\")",
+                "language": "g.addV(\"a\", \"b\")",
+                "canonical": "g.addV(\"a\", \"b\")",
+                "anonymized": "g.addV(string0, string1)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\")",
+                "go": "g.AddV(\"a\", \"b\")",
+                "groovy": "g.addV(\"a\", \"b\")",
+                "java": "g.addV(\"a\", \"b\")",
+                "javascript": "g.addV(\"a\", \"b\")",
+                "python": "g.add_v('a', 'b')"
+            },
+            {
+                "original": "g.V().dropLabels().labels()",
+                "language": "g.V().dropLabels().labels()",
+                "canonical": "g.V().dropLabels().labels()",
+                "anonymized": "g.V().dropLabels().labels()",
+                "dotnet": "g.V().DropLabels().Labels()",
+                "go": "g.V().DropLabels().Labels()",
+                "groovy": "g.V().dropLabels().labels()",
+                "java": "g.V().dropLabels().labels()",
+                "javascript": "g.V().dropLabels().labels()",
+                "python": "g.V().drop_labels().labels()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_V_dropLabelXa_bX_labels",
+        "traversals": [
+            {
+                "original": "g.addV(\"a\", \"b\", \"c\")",
+                "language": "g.addV(\"a\", \"b\", \"c\")",
+                "canonical": "g.addV(\"a\", \"b\", \"c\")",
+                "anonymized": "g.addV(string0, string1, string2)",
+                "dotnet": "g.AddV((string) \"a\", (string) \"b\", (string) \"c\")",
+                "go": "g.AddV(\"a\", \"b\", \"c\")",
+                "groovy": "g.addV(\"a\", \"b\", \"c\")",
+                "java": "g.addV(\"a\", \"b\", \"c\")",
+                "javascript": "g.addV(\"a\", \"b\", \"c\")",
+                "python": "g.add_v('a', 'b', 'c')"
+            },
+            {
+                "original": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "language": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "canonical": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "anonymized": "g.V().dropLabel(string0, string1).labels()",
+                "dotnet": "g.V().DropLabel(\"a\", \"b\").Labels()",
+                "go": "g.V().DropLabel(\"a\", \"b\").Labels()",
+                "groovy": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "java": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "javascript": "g.V().dropLabel(\"a\", \"b\").labels()",
+                "python": "g.V().drop_label('a', 'b').labels()"
+            }
+        ]
+    },
+    {
+        "scenario": "g_V_dropLabels_defaultLabel",
+        "traversals": [
+            {
+                "original": "g.addV(\"person\")",
+                "language": "g.addV(\"person\")",
+                "canonical": "g.addV(\"person\")",
+                "anonymized": "g.addV(string0)",
+                "dotnet": "g.AddV((string) \"person\")",
+                "go": "g.AddV(\"person\")",
+                "groovy": "g.addV(\"person\")",
+                "java": "g.addV(\"person\")",
+                "javascript": "g.addV(\"person\")",
+                "python": "g.add_v('person')"
+            },
+            {
+                "original": "g.V().dropLabels().labels()",
+                "language": "g.V().dropLabels().labels()",
+                "canonical": "g.V().dropLabels().labels()",
+                "anonymized": "g.V().dropLabels().labels()",
+                "dotnet": "g.V().DropLabels().Labels()",
+                "go": "g.V().DropLabels().Labels()",
+                "groovy": "g.V().dropLabels().labels()",
+                "java": "g.V().dropLabels().labels()",
+                "javascript": "g.V().dropLabels().labels()",
+                "python": "g.V().drop_labels().labels()"
+            }
+        ]
+    },
     {
         "scenario": "g_V_fail",
         "traversals": [
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/AddVertex.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/AddVertex.feature
index 99e1492f56..0d7fdaf2c7 100644
--- a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/AddVertex.feature
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/AddVertex.feature
@@ -703,4 +703,27 @@ Feature: Step - addV()
     When iterated to list
     Then the result should be unordered
       | result |
-      | d[2010].i |
\ No newline at end of file
+      | d[2010].i |
+
+  @MultiLabel
+  Scenario: g_addVXa_bX_labels
+    Given the empty graph
+    And the traversal of
+      """
+      g.addV("a", "b").labels().fold()
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V().hasLabel(\"a\").hasLabel(\"b\")"
+
+  @MultiLabel
+  Scenario: g_addVXa_b_cX_labels_count
+    Given the empty graph
+    And the traversal of
+      """
+      g.addV("a", "b", "c").labels().count()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | d[3].l |
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/Labels.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/Labels.feature
new file mode 100644
index 0000000000..322d0ca42c
--- /dev/null
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/Labels.feature
@@ -0,0 +1,110 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+@StepClassMap @StepLabels @MultiLabel
+Feature: Step - labels()
+
+  @MultiLabel
+  Scenario: g_V_hasLabelXpersonX_labels
+    Given the modern graph
+    And the traversal of
+      """
+      g.V().hasLabel("person").labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | person |
+      | person |
+      | person |
+      | person |
+
+  @MultiLabel
+  Scenario: g_addVXa_bX_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b")
+      """
+    And the traversal of
+      """
+      g.V().labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | a |
+      | b |
+
+  @MultiLabel
+  Scenario: g_addVXa_bX_labels_fold
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b")
+      """
+    And the traversal of
+      """
+      g.V().labels().fold()
+      """
+    When iterated to list
+    Then the result should have a count of 1
+
+  @MultiLabel
+  Scenario: g_addVXa_bX_labels_count
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b")
+      """
+    And the traversal of
+      """
+      g.V().labels().count()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | d[2].l |
+
+  @MultiLabel
+  Scenario: g_addV_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV()
+      """
+    And the traversal of
+      """
+      g.V().labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | vertex |
+
+  @MultiLabel
+  Scenario: g_E_labels
+    Given the modern graph
+    And the traversal of
+      """
+      g.E().hasLabel("knows").labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | knows |
+      | knows |
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MergeVertex.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MergeVertex.feature
index 801b39db7f..930e3a181b 100644
--- a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MergeVertex.feature
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MergeVertex.feature
@@ -990,3 +990,127 @@ Feature: Step - mergeV()
     Then the result should have a count of 1
     And the graph should return 1 for count of "g.V().has(\"person\",\"name\",\"stephen\").hasNot(\"created\")"
     And the graph should return 2 for count of "g.V()"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_ab_name_markoX_multilabel_create
+    Given the empty graph
+    And the traversal of
+      """
+      g.mergeV([(T.label): ["person","employee"], name: "marko"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"person\").hasLabel(\"employee\")"
+    And the graph should return 1 for count of "g.V().has(\"name\",\"marko\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_abc_name_testX_multilabel_create
+    Given the empty graph
+    And the traversal of
+      """
+      g.mergeV([(T.label): ["a","b","c"], name: "test"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"a\").hasLabel(\"b\").hasLabel(\"c\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_person_name_markoX_single_label
+    Given the empty graph
+    And the traversal of
+      """
+      g.mergeV([(T.label): "person", name: "marko"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"person\")"
+    And the graph should return 1 for count of "g.V().has(\"name\",\"marko\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_ab_name_markoX_multilabel_match
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").addLabel("employee").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.mergeV([(T.label): ["person","employee"], name: "marko"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"person\").hasLabel(\"employee\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_ab_name_markoX_multilabel_nomatch
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.mergeV([(T.label): ["person","employee"], name: "marko"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 2 for count of "g.V()"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_person_name_markoX_optionXonMatch_label_managerX
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").addLabel("employee").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.mergeV([(T.label): "person", name: "marko"]).
+          option(Merge.onMatch, [(T.label): "manager"])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"manager\")"
+    And the graph should return 0 for count of "g.V().hasLabel(\"person\")"
+    And the graph should return 0 for count of "g.V().hasLabel(\"employee\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_person_name_markoX_optionXonMatch_label_manager_directorX
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.mergeV([(T.label): "person", name: "marko"]).
+          option(Merge.onMatch, [(T.label): ["manager","director"]])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"manager\").hasLabel(\"director\")"
+    And the graph should return 0 for count of "g.V().hasLabel(\"person\")"
+
+  @MultiLabel
+  Scenario: g_mergeVXlabel_person_name_markoX_optionXonMatch_label_emptyX
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.mergeV([(T.label): "person", name: "marko"]).
+          option(Merge.onMatch, [(T.label): []])
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V()"
+    And the graph should return 1 for count of "g.V().hasLabel(\"vertex\")"
+    And the graph should return 0 for count of "g.V().hasLabel(\"person\")"
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/AddLabel.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/AddLabel.feature
new file mode 100644
index 0000000000..821b80ab72
--- /dev/null
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/AddLabel.feature
@@ -0,0 +1,66 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+@StepClassSideEffect @StepAddLabel @MultiLabel
+Feature: Step - addLabel()
+
+  @MultiLabel
+  Scenario: g_V_hasLabelXpersonX_hasXname_markoX_addLabelXemployeeX_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person").property("name", "marko")
+      """
+    And the traversal of
+      """
+      g.V().hasLabel("person").has("name", "marko").addLabel("employee").labels().fold()
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 1 for count of "g.V().hasLabel(\"person\").hasLabel(\"employee\")"
+
+  @MultiLabel
+  Scenario: g_V_addLabelXa_bX_labels_count
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person")
+      """
+    And the traversal of
+      """
+      g.V().addLabel("a", "b").labels().count()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | d[3].l |
+
+  @MultiLabel
+  Scenario: g_V_addLabelXexistingX_labels_count
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person")
+      """
+    And the traversal of
+      """
+      g.V().addLabel("person").labels().count()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | d[1].l |
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/DropLabel.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/DropLabel.feature
new file mode 100644
index 0000000000..051cc793af
--- /dev/null
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/sideEffect/DropLabel.feature
@@ -0,0 +1,83 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+@StepClassSideEffect @StepDropLabel @MultiLabel
+Feature: Step - dropLabel() / dropLabels()
+
+  @MultiLabel
+  Scenario: g_V_dropLabelXaX_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b")
+      """
+    And the traversal of
+      """
+      g.V().dropLabel("a").labels().fold()
+      """
+    When iterated to list
+    Then the result should have a count of 1
+    And the graph should return 0 for count of "g.V().hasLabel(\"a\")"
+    And the graph should return 1 for count of "g.V().hasLabel(\"b\")"
+
+  @MultiLabel
+  Scenario: g_V_dropLabels_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b")
+      """
+    And the traversal of
+      """
+      g.V().dropLabels().labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | vertex |
+
+  @MultiLabel
+  Scenario: g_V_dropLabelXa_bX_labels
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("a", "b", "c")
+      """
+    And the traversal of
+      """
+      g.V().dropLabel("a", "b").labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | c |
+
+  @MultiLabel
+  Scenario: g_V_dropLabels_defaultLabel
+    Given the empty graph
+    And the graph initializer of
+      """
+      g.addV("person")
+      """
+    And the traversal of
+      """
+      g.V().dropLabels().labels()
+      """
+    When iterated to list
+    Then the result should be unordered
+      | result |
+      | vertex |
diff --git a/gremlin-test/src/test/java/org/apache/tinkerpop/gremlin/structure/ExceptionCoverageTest.java b/gremlin-test/src/test/java/org/apache/tinkerpop/gremlin/structure/ExceptionCoverageTest.java
index a8f3946128..17b8b020dc 100644
--- a/gremlin-test/src/test/java/org/apache/tinkerpop/gremlin/structure/ExceptionCoverageTest.java
+++ b/gremlin-test/src/test/java/org/apache/tinkerpop/gremlin/structure/ExceptionCoverageTest.java
@@ -75,6 +75,9 @@ public class ExceptionCoverageTest {
             add("org.apache.tinkerpop.gremlin.structure.Element$Exceptions#elementAlreadyRemoved"); // as of 3.1.0
             add("org.apache.tinkerpop.gremlin.structure.Graph$Exceptions#traversalEngineNotSupported"); // as of 3.2.0
 
+            // this is a general default exception for providers that don't support label mutation:
+            add("org.apache.tinkerpop.gremlin.structure.Element$Exceptions#labelMutationNotSupported");
+
             // need to write consistency tests for the following items still...........
             add("org.apache.tinkerpop.gremlin.process.computer.GraphComputer$Exceptions#supportsDirectObjects");
         }};
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/AbstractTinkerGraph.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/AbstractTinkerGraph.java
index a77edac34d..5a0abb6d13 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/AbstractTinkerGraph.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/AbstractTinkerGraph.java
@@ -354,6 +354,26 @@ public abstract class AbstractTinkerGraph implements Graph {
 
     protected abstract void addInEdge(final TinkerVertex vertex, final String label, final Edge edge);
 
+    /**
+     * Add an edge to the per-vertex adjacency maps under the given label.
+     * Used when labels are added to an existing edge.
+     *
+     * @param edge  the edge to register
+     * @param label the label under which to register the edge
+     * @since 4.0.0
+     */
+    public abstract void addEdgeToAdjacency(final TinkerEdge edge, final String label);
+
+    /**
+     * Remove an edge from the per-vertex adjacency maps for the given label.
+     * Used when labels are removed from an existing edge.
+     *
+     * @param edge  the edge to unregister
+     * @param label the label from which to unregister the edge
+     * @since 4.0.0
+     */
+    public abstract void removeEdgeFromAdjacency(final TinkerEdge edge, final String label);
+
     /**
      * Called when a vertex's labels are modified to allow the graph to update any internal label indices.
      * The default implementation is a no-op since TinkerGraph does not maintain a separate label index.
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerEdge.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerEdge.java
index 3ced83454e..663908af0e 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerEdge.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerEdge.java
@@ -30,6 +30,7 @@ import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.util.Collections;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
@@ -40,6 +41,7 @@ import java.util.stream.Collectors;
  */
 public class TinkerEdge extends TinkerElement implements Edge {
 
+    protected final Set<String> edgeLabels;
     protected Map<String, Property> properties;
 
     protected Vertex inVertex = null;
@@ -62,8 +64,30 @@ public class TinkerEdge extends TinkerElement implements Edge {
         }
     }
 
+    protected TinkerEdge(final Object id, final Vertex outVertex, final Set<String> labels, final Vertex inVertex) {
+        this(id, outVertex, labels, inVertex, 0);
+    }
+
+    protected TinkerEdge(final Object id, final Vertex outVertex, final Set<String> labels, final Vertex inVertex, final long currentVersion) {
+        this(id, (AbstractTinkerGraph) outVertex.graph(), outVertex.id(),
+             (labels == null || labels.isEmpty()) ? Edge.DEFAULT_LABEL : labels.iterator().next(),
+             inVertex.id(), currentVersion, false);
+        this.edgeLabels.clear();
+        if (labels != null && !labels.isEmpty()) {
+            this.edgeLabels.addAll(labels);
+        } else {
+            this.edgeLabels.add(Edge.DEFAULT_LABEL);
+        }
+        if (!isTxMode) {
+            this.inVertex = inVertex;
+            this.outVertex = outVertex;
+        }
+    }
+
     private TinkerEdge(final Object id, AbstractTinkerGraph graph, final Object outVertexId, final String label, final Object inVertexId, final long currentVersion, final Boolean skipIndexUpdate) {
         super(id, label, currentVersion);
+        this.edgeLabels = ConcurrentHashMap.newKeySet();
+        this.edgeLabels.add(label);
         isTxMode = graph instanceof TinkerTransactionGraph;
         this.graph = graph;
         if (isTxMode) {
@@ -107,7 +131,66 @@ public class TinkerEdge extends TinkerElement implements Edge {
 
     @Override
     public Set<String> labels() {
-        return Collections.singleton(this.label);
+        return Collections.unmodifiableSet(this.edgeLabels);
+    }
+
+    @Override
+    @Deprecated
+    public String label() {
+        return this.edgeLabels.iterator().next();
+    }
+
+    @Override
+    public void addLabel(final String label, final String... labels) {
+        graph.touch(this);
+        ElementHelper.validateLabel(label);
+        for (final String l : labels) {
+            ElementHelper.validateLabel(l);
+        }
+        // Remove default label if it was the only label
+        if (this.edgeLabels.size() == 1 && this.edgeLabels.contains(Edge.DEFAULT_LABEL)) {
+            this.graph.removeEdgeFromAdjacency(this, Edge.DEFAULT_LABEL);
+            this.edgeLabels.remove(Edge.DEFAULT_LABEL);
+        }
+        this.edgeLabels.add(label);
+        this.graph.addEdgeToAdjacency(this, label);
+        for (final String l : labels) {
+            this.edgeLabels.add(l);
+            this.graph.addEdgeToAdjacency(this, l);
+        }
+        this.label = this.edgeLabels.iterator().next();
+    }
+
+    @Override
+    public void dropLabels() {
+        graph.touch(this);
+        for (final String l : new LinkedHashSet<>(this.edgeLabels)) {
+            this.graph.removeEdgeFromAdjacency(this, l);
+        }
+        this.edgeLabels.clear();
+        this.edgeLabels.add(Edge.DEFAULT_LABEL);
+        this.graph.addEdgeToAdjacency(this, Edge.DEFAULT_LABEL);
+        this.label = this.edgeLabels.iterator().next();
+    }
+
+    @Override
+    public void dropLabel(final String label, final String... labels) {
+        graph.touch(this);
+        if (this.edgeLabels.contains(label)) {
+            this.graph.removeEdgeFromAdjacency(this, label);
+            this.edgeLabels.remove(label);
+        }
+        for (final String l : labels) {
+            if (this.edgeLabels.contains(l)) {
+                this.graph.removeEdgeFromAdjacency(this, l);
+                this.edgeLabels.remove(l);
+            }
+        }
+        if (this.edgeLabels.isEmpty()) {
+            this.edgeLabels.add(Edge.DEFAULT_LABEL);
+            this.graph.addEdgeToAdjacency(this, Edge.DEFAULT_LABEL);
+        }
+        this.label = this.edgeLabels.iterator().next();
     }
 
     @Override
@@ -129,11 +212,15 @@ public class TinkerEdge extends TinkerElement implements Edge {
         if (!isTxMode) {
             // shallow copy for non-tx mode
             final TinkerEdge edge = new TinkerEdge(id, outVertex, label, inVertex, currentVersion);
+            edge.edgeLabels.clear();
+            edge.edgeLabels.addAll(this.edgeLabels);
             edge.properties = properties;
             return edge;
         }
 
         final TinkerEdge edge = new TinkerEdge(id, graph, outVertexId, label, inVertexId, currentVersion, true);
+        edge.edgeLabels.clear();
+        edge.edgeLabels.addAll(this.edgeLabels);
 
         if (properties != null) {
             final Map<String, Property> cloned = new ConcurrentHashMap<>(properties.size());
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerElement.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerElement.java
index 8aa2d1db03..d8587b71fa 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerElement.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerElement.java
@@ -27,7 +27,7 @@ import org.apache.tinkerpop.gremlin.structure.util.ElementHelper;
 public abstract class TinkerElement implements Element {
 
     protected final Object id;
-    protected final String label;
+    protected String label;
     protected boolean removed = false;
     protected long currentVersion;
 
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java
index ffe328f98e..3b493caa5d 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java
@@ -330,6 +330,36 @@ public class TinkerGraph extends AbstractTinkerGraph {
         edges.add(edge);
     }
 
+    @Override
+    public void addEdgeToAdjacency(final TinkerEdge edge, final String label) {
+        final TinkerVertex outV = (TinkerVertex) edge.outVertex();
+        final TinkerVertex inV = (TinkerVertex) edge.inVertex();
+        if (null == outV.outEdges) outV.outEdges = new HashMap<>();
+        outV.outEdges.computeIfAbsent(label, k -> new HashSet<>()).add(edge);
+        if (null == inV.inEdges) inV.inEdges = new HashMap<>();
+        inV.inEdges.computeIfAbsent(label, k -> new HashSet<>()).add(edge);
+    }
+
+    @Override
+    public void removeEdgeFromAdjacency(final TinkerEdge edge, final String label) {
+        final TinkerVertex outV = (TinkerVertex) edge.outVertex();
+        final TinkerVertex inV = (TinkerVertex) edge.inVertex();
+        if (outV.outEdges != null) {
+            final Set<Edge> edges = outV.outEdges.get(label);
+            if (edges != null) {
+                edges.remove(edge);
+                if (edges.isEmpty()) outV.outEdges.remove(label);
+            }
+        }
+        if (inV.inEdges != null) {
+            final Set<Edge> edges = inV.inEdges.get(label);
+            if (edges != null) {
+                edges.remove(edge);
+                if (edges.isEmpty()) inV.inEdges.remove(label);
+            }
+        }
+    }
+
     /**
      * Return TinkerGraph feature set.
      * <p/>
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerTransactionGraph.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerTransactionGraph.java
index d7914981d5..a223607fe2 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerTransactionGraph.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerTransactionGraph.java
@@ -139,7 +139,8 @@ public final class TinkerTransactionGraph extends AbstractTinkerGraph {
         Object idValue = vertexIdManager.convert(ElementHelper.getIdValue(keyValues).orElse(null));
         if (null == idValue)
             idValue = vertexIdManager.getNextId(this);
-        final String label = ElementHelper.getLabelValue(keyValues).orElse(Vertex.DEFAULT_LABEL);
+        final Set<String> labels = ElementHelper.getLabelsValue(keyValues).orElse(
+                Collections.singleton(Vertex.DEFAULT_LABEL));
 
         this.tx().readWrite();
         final long txNumber = transaction.getTxNumber();
@@ -164,7 +165,7 @@ public final class TinkerTransactionGraph extends AbstractTinkerGraph {
         if (container == null)
             container = newContainer;
 
-        final TinkerVertex vertex = new TinkerVertex(idValue, label, this, version);
+        final TinkerVertex vertex = new TinkerVertex(idValue, labels, this, version);
         ElementHelper.attachProperties(vertex, VertexProperty.Cardinality.list, keyValues);
         container.setDraft(vertex, (TinkerTransaction) tx());
 
@@ -410,6 +411,40 @@ public final class TinkerTransactionGraph extends AbstractTinkerGraph {
         edges.add(edge.id());
     }
 
+    @Override
+    public void addEdgeToAdjacency(final TinkerEdge edge, final String label) {
+        final TinkerVertex outV = (TinkerVertex) edge.outVertex();
+        final TinkerVertex inV = (TinkerVertex) edge.inVertex();
+        touch(outV);
+        touch(inV);
+        if (null == outV.outEdgesId) outV.outEdgesId = new ConcurrentHashMap<>();
+        outV.outEdgesId.computeIfAbsent(label, k -> ConcurrentHashMap.newKeySet()).add(edge.id());
+        if (null == inV.inEdgesId) inV.inEdgesId = new ConcurrentHashMap<>();
+        inV.inEdgesId.computeIfAbsent(label, k -> ConcurrentHashMap.newKeySet()).add(edge.id());
+    }
+
+    @Override
+    public void removeEdgeFromAdjacency(final TinkerEdge edge, final String label) {
+        final TinkerVertex outV = (TinkerVertex) edge.outVertex();
+        final TinkerVertex inV = (TinkerVertex) edge.inVertex();
+        touch(outV);
+        touch(inV);
+        if (outV.outEdgesId != null) {
+            final Set<Object> edges = outV.outEdgesId.get(label);
+            if (edges != null) {
+                edges.remove(edge.id());
+                if (edges.isEmpty()) outV.outEdgesId.remove(label);
+            }
+        }
+        if (inV.inEdgesId != null) {
+            final Set<Object> edges = inV.inEdgesId.get(label);
+            if (edges != null) {
+                edges.remove(edge.id());
+                if (edges.isEmpty()) inV.inEdgesId.remove(label);
+            }
+        }
+    }
+
     /**
      * Return TinkerGraph feature set.
      * <p/>
diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertex.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertex.java
index b10ebe1e7b..457db2cc94 100644
--- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertex.java
+++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertex.java
@@ -61,36 +61,32 @@ public class TinkerVertex extends TinkerElement implements Vertex {
     protected final Set<String> vertexLabels;
 
     protected TinkerVertex(final Object id, final String label, final AbstractTinkerGraph graph) {
-        super(id, label);
-        this.graph = graph;
-        this.isTxMode = graph instanceof TinkerTransactionGraph;
-        this.allowNullPropertyValues = graph.features().vertex().supportsNullPropertyValues();
-        this.vertexLabels = ConcurrentHashMap.newKeySet();
-        this.vertexLabels.add(null == label ? Vertex.DEFAULT_LABEL : label);
+        this(id, Collections.singleton(label != null ? label : Vertex.DEFAULT_LABEL), graph, -1);
     }
 
     protected TinkerVertex(final Object id, final String label, final AbstractTinkerGraph graph, final long currentVersion) {
-        super(id, label, currentVersion);
-        this.graph = graph;
-        this.isTxMode = graph instanceof TinkerTransactionGraph;
-        this.allowNullPropertyValues = graph.features().vertex().supportsNullPropertyValues();
-        this.vertexLabels = ConcurrentHashMap.newKeySet();
-        this.vertexLabels.add(null == label ? Vertex.DEFAULT_LABEL : label);
+        this(id, Collections.singleton(label != null ? label : Vertex.DEFAULT_LABEL), graph, currentVersion);
     }
 
     /**
      * Constructs a TinkerVertex with multiple labels.
      */
     protected TinkerVertex(final Object id, final Set<String> labels, final AbstractTinkerGraph graph) {
-        super(id, (labels == null || labels.isEmpty()) ? Vertex.DEFAULT_LABEL : labels.iterator().next());
+        this(id, labels, graph, -1);
+    }
+
+    /**
+     * Canonical constructor. Constructs a TinkerVertex with multiple labels and a specific version (for transactional graphs).
+     */
+    protected TinkerVertex(final Object id, final Set<String> labels, final AbstractTinkerGraph graph, final long currentVersion) {
+        super(id, (labels == null || labels.isEmpty()) ? Vertex.DEFAULT_LABEL : labels.iterator().next(), currentVersion);
         this.graph = graph;
         this.isTxMode = graph instanceof TinkerTransactionGraph;
         this.allowNullPropertyValues = graph.features().vertex().supportsNullPropertyValues();
+        this.vertexLabels = ConcurrentHashMap.newKeySet();
         if (labels == null || labels.isEmpty()) {
-            this.vertexLabels = ConcurrentHashMap.newKeySet();
             this.vertexLabels.add(Vertex.DEFAULT_LABEL);
         } else {
-            this.vertexLabels = ConcurrentHashMap.newKeySet();
             this.vertexLabels.addAll(labels);
         }
     }
@@ -120,6 +116,7 @@ public class TinkerVertex extends TinkerElement implements Vertex {
 
         this.vertexLabels.add(label);
         Collections.addAll(this.vertexLabels, labels);
+        this.label = this.vertexLabels.iterator().next();
         this.graph.updateVertexLabelIndex(this);
     }
 
@@ -127,6 +124,7 @@ public class TinkerVertex extends TinkerElement implements Vertex {
     public void dropLabels() {
         this.vertexLabels.clear();
         this.vertexLabels.add(Vertex.DEFAULT_LABEL);
+        this.label = this.vertexLabels.iterator().next();
         this.graph.updateVertexLabelIndex(this);
     }
 
@@ -140,6 +138,7 @@ public class TinkerVertex extends TinkerElement implements Vertex {
         if (this.vertexLabels.isEmpty()) {
             this.vertexLabels.add(Vertex.DEFAULT_LABEL);
         }
+        this.label = this.vertexLabels.iterator().next();
         this.graph.updateVertexLabelIndex(this);
     }
 
@@ -153,9 +152,7 @@ public class TinkerVertex extends TinkerElement implements Vertex {
             return vertex;
         }
 
-        final TinkerVertex vertex = new TinkerVertex(id, label, graph, currentVersion);
-        vertex.vertexLabels.clear();
-        vertex.vertexLabels.addAll(this.vertexLabels);
+        final TinkerVertex vertex = new TinkerVertex(id, new LinkedHashSet<>(vertexLabels), graph, currentVersion);
         if (inEdgesId != null)
             vertex.inEdgesId = CollectionUtil.clone((ConcurrentHashMap<String, Set<Object>>) inEdgesId);
 
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/sideEffect/LabelMutationStepTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/sideEffect/LabelMutationStepTest.java
index 58ff4fbce1..7ac5c88015 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/sideEffect/LabelMutationStepTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/sideEffect/LabelMutationStepTest.java
@@ -78,12 +78,14 @@ public class LabelMutationStepTest {
         assertThat(v.labels(), containsInAnyOrder("person", "manager"));
     }
 
-    @Test(expected = UnsupportedOperationException.class)
-    public void shouldThrowWhenAddingLabelToEdgeViaTraversal() {
+    @Test
+    public void shouldAddLabelToEdgeViaTraversal() {
         final Vertex v1 = g.addV("person").next();
         final Vertex v2 = g.addV("person").next();
-        v1.addEdge("knows", v2);
+        final Edge e = v1.addEdge("knows", v2);
         g.E().addLabel("friend").iterate();
+        assertThat(e.labels(), hasSize(2));
+        assertThat(e.labels(), containsInAnyOrder("knows", "friend"));
     }
 
     // --- dropLabel step tests ---
@@ -112,12 +114,14 @@ public class LabelMutationStepTest {
         assertThat(v.labels(), containsInAnyOrder("employee"));
     }
 
-    @Test(expected = UnsupportedOperationException.class)
-    public void shouldThrowWhenDroppingLabelsOnEdgeViaTraversal() {
+    @Test
+    public void shouldDropLabelsOnEdgeViaTraversal() {
         final Vertex v1 = g.addV("person").next();
         final Vertex v2 = g.addV("person").next();
-        v1.addEdge("knows", v2);
+        final Edge e = v1.addEdge("knows", v2);
         g.E().dropLabels().iterate();
+        assertThat(e.labels(), hasSize(1));
+        assertThat(e.labels(), containsInAnyOrder(Edge.DEFAULT_LABEL));
     }
 
     // --- addV multi-label tests ---
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertexMultiLabelTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertexMultiLabelTest.java
index 5fc84f8de2..27387d60e9 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertexMultiLabelTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerVertexMultiLabelTest.java
@@ -147,20 +147,24 @@ public class TinkerVertexMultiLabelTest {
         assertThat(v.labels(), containsInAnyOrder(Vertex.DEFAULT_LABEL));
     }
 
-    @Test(expected = UnsupportedOperationException.class)
-    public void shouldThrowWhenAddingLabelToEdge() {
+    @Test
+    public void shouldAddLabelToEdge() {
         final Vertex v1 = g.addV("person").next();
         final Vertex v2 = g.addV("person").next();
         final Edge e = v1.addEdge("knows", v2);
         e.addLabel("friend");
+        assertThat(e.labels(), hasSize(2));
+        assertThat(e.labels(), containsInAnyOrder("knows", "friend"));
     }
 
-    @Test(expected = UnsupportedOperationException.class)
-    public void shouldThrowWhenDroppingLabelsOnEdge() {
+    @Test
+    public void shouldDropLabelsOnEdge() {
         final Vertex v1 = g.addV("person").next();
         final Vertex v2 = g.addV("person").next();
         final Edge e = v1.addEdge("knows", v2);
         e.dropLabels();
+        assertThat(e.labels(), hasSize(1));
+        assertThat(e.labels(), containsInAnyOrder(Edge.DEFAULT_LABEL));
     }
 
     @Test