Why does my code take different values when i switch the order in a set (knowing that order doesn't matter with sets)

When we say that sets have no order or that order doesn't matter, it means that {x, y} == {y, x}. But (a, b) and (b, a) are tuples, order matters for them, so (a, b) != (b, a) and therefore {(a, b), (b, a)} is a set with two distinct elements, although it's equal to {(b, a), (a, b)}.

When your code looks like this:

        if (adj_node, key) not in edges:
            edge = (key, adj_node)
            edges.add(edge)

then when the edge a <-> b is first encountered, it's as (key, adj_node) == (a, b) and is added to the set. When it's encountered the second (and only other) time, it's as (key, adj_node) == (b, a), meaning (adj_node, key) == (a, b) which is already in the set so (adj_node, key) not in edges is false and (b, a) doesn't get added to the set.

I think it just needs a little change, try this:

def get_edges(self):
    edges = set()
    for key in self.graph:
        for adj_node in self.graph[key]:
            if ((key, adj_node) not in edges) and ((adj_node, key) not in edges):
                edge = (key, adj_node)
                edges.add(edge)
            else:
                pass
    return edges

Update:
So it is an Undigraph.
And it's me overcomplicated this.
And your way is actually better than my checking both ways.

The reason your code succeed, is that set will only contain one instance of any value.
So each time do the add, if there's already same tuple exists, it simply won't change the set.
And you already used the if to check the tuple of opposite direction, so it won't create duplicate edges.

For example, when (a, b) hits the if checking, it will check (b,a) exists in the set or not, if exists, then pass. If not, add (a, b) in the set, if (a, b) exists, the set won't change since only one instace will be in the set.
And later when looped to (b, a), since (a, b) already in the set, the if will be false and passed.
So by this way, the set is safe, free of duplicate edges.