I have investigate further and many things depends on what exactly you want to do on which resource. Documentation might be hard to understand so I will expand it more in this answer.

Background

You are referring to Merge Patch where you have example of merge patching (adding additional container) spec.template.spec.containers. Below you have Notes on the strategic merge patch.

The patch you did in the preceding exercise is called a strategic merge patch. Notice that the patch did not replace the containers list. Instead it added a new Container to the list. In other words, the list in the patch was merged with the existing list. This is not always what happens when you use a strategic merge patch on a list. In some cases, the list is replaced, not merged.

With a strategic merge patch, a list is either replaced or merged depending on its patch strategy. The patch strategy is specified by the value of the patchStrategy key in a field tag in the Kubernetes source code.

Default patch strategy can be found in Kubernetes API documentation or in the Kubernetes source code

Regarding patching Deployments labels, since apiVersion: apps/v1 it's impossible. You can find confirmation in Deployments - Label selector updates.

Note: In API version apps/v1, a Deployment's label selector is immutable after it gets created.

If you would try to update or patch it in apiVersion: apps/v1 you will get an field is immutable error. Only way to change labels/selectors is to redeploy whole Deployment.

However, if you would use older Kubernetes version with apiVersion: extensions/v1beta1 it could be patched like in Github example.

Please keep in mind that you also can use more patching methods like JSON merge patch or merge patch using the retainKeys strategy.

Tests

Based on Documentation Deployment Example.

You cannot change Deployment labels in apiVersion: apps/v1, thus you cannot patch it as well.

$ kubectl apply -f nginx-second.yaml
The Deployment "nginx-deployment" is invalid: spec.selector: Invalid value: v1.LabelSelector{MatchLabels:map[string]string{"app":"nginx", "test":"test"}, MatchExpressions:[]v1.LabelSelectorRequirement(nil)}: field is immutable

In comments you referred to Node Selector which can be patched like in this stackoverflow thread.

In documentaton Use a strategic merge patch to update a Deployment you can find 2 examples, container which patchStrategy:"merge":

The patch strategy is specified by the value of the patchStrategy key in a field tag in the Kubernetes source code. For example, the Containers field of PodSpec struct has a patchStrategy of merge:

type PodSpec struct {
  ...
  Containers []Container `json:"containers" patchStrategy:"merge" patchMergeKey:"name" ...`

and tolerations example which empty patchStrategy field.

Notice that the tolerations list in the PodSpec was replaced, not merged. This is because the Tolerations field of PodSpec does not have a patchStrategy key in its field tag. So the strategic merge patch uses the default patch strategy, which is replace.

type PodSpec struct {
  ...
  Tolerations []Toleration `json:"tolerations,omitempty" protobuf:"bytes,22,opt,name=tolerations"`

Both examples (with containers and tolerations) are list but difference is when you are using merge it's adding new ones, but when you want to replace, key value must be the same.

patch-tolerations.yaml

$ cat patch-tolerations.yaml
spec:
  template:
    spec:
      tolerations:
      - effect: NoSchedule
        key: disktype
        value: ssd
        test1: testvalue1
        test2: testvalue2
        test3: testvalue3

Replacing using the same keys

$ kubectl get deploy patch-demo -o yaml | grep tolerations: -A 5
      tolerations:
      - effect: NoSchedule
        key: dedicated
        value: test-team

$ kubectl patch deployment patch-demo --patch "$(cat patch-tolerations.yaml)"

$ kubectl get deploy patch-demo -o yaml | grep tolerations: -A 5
      tolerations:
      - effect: NoSchedule
        key: disktype
        value: ssd

It replaced only values with the same key. If you would change patch-tolerations.yaml to

spec:
  template:
    spec:
      tolerations:
      - effect: NoSchedule
        test1: testvalue1
        test2: testvalue2
        test3: testvalue3

You will get an error:

$ kubectl patch deployment patch-demo --patch "$(cat patch-tolerations.yaml)"
The Deployment "patch-demo" is invalid: spec.template.spec.tolerations[0].operator: Invalid value: "": operator must be Exists when `key` is empty, which means "match all value
s and all keys"

Tests on StatefulSet

As you asked about labels, you can change them in statefulset. Based on example from Docs Creating a StatefulSet with some additional annotations metadata.labels.

$ kubectl get sts -oyaml | grep labels: -A 3
    labels:
      test: test
      test1: test1
    name: web
--
        labels:
          app: nginx
      spec:
        containers:
---
$ cat patch-sts.yaml
metadata:
  labels:
    run: runtest
    app: apptest
$ cat patch-sts-template.yaml
spec:
  template:
    metadata:
      labels:
        app: nginx
        app2: run
        test: test
---
$ kubectl patch sts web --patch "$(cat patch-sts.yaml)"
statefulset.apps/web patched
$ kubectl patch sts web --patch "$(cat patch-sts-template.yaml)"
statefulset.apps/web patched

$ kubectl get sts -oyaml | grep labels: -A 5
    labels:
      app: apptest
      run: runtest
      test: test
      test1: test1
    name: web
--
        labels:
          app: nginx
          app2: run
          test: test
      spec:
        containers:

Conclusion

You are not able to change Deployment labels as those fields are immutable.

When you want to patch something, you have to check which is default patchStrategy.

The patch strategy is specified by the value of the patchStrategy key in a field tag in the Kubernetes source code.

In merge patch all informations are mixing, when using replace patch, new and old patching objects must have the same key.

You can use a few patch methods:

• Strategic merge patch

  In other words, the list in the patch was merged with the existing list.

• JSON merge patch

  A strategic merge patch is different from a JSON merge patch. With a JSON merge patch, if you want to update a list, you have to specify the entire new list. And the new list completely replaces the existing list.

• Strategic merge patch using the retainKeys.

If this didn't answer your question, please specify what you want to exactly achieve using which version, resource and what you want to patch.