Normal has societal connotations and can vary according to perception, experience, culture, politics and period of history, whilst average usually refers to the results of statistical measurements related to groups of people.
I think your description of why you used each article is very close.
In general, we use "the" when the thing is the only one, or we are referring to a specific one. We use "a" when it is an indefinite one of many. Whether there is one or many depends on context: When we use "the", we are not necessarily saying that this is the only one in the history of the universe, but the only one relevant in the present context.
For example: (a) "I entered a room full of strangers. A man named John approached me." There could be many men named "John" there, so I should use the indefinite article. (b) "I met three men who said their names were Bob, Paul, and John. The man named John approached me." Now in context there is only one relevant man named "John", so I should use the definite article.
In your example, the first sentence introduces the tree and the vertex. So at that instant, they are indefinite. But once you have introduced them, they become definite. So the first reference is "a tree T" but after that it becomes "the tree T". Now that you have named it, there is only one. (This assumes that you do not have two trees and call them both T. As in a context like this you're inventing the names, I assume you would not do this.) The same would apply in more conventional contexts. "I entered a room full of strangers. A [indefinite] tall man approached me. The [definite] tall man said ..." Once the context narrows the focus to an individual example, it becomes "the".
The vertex is "a" leaf because at this point in the context, the tree could have many leaves. So it is one of many. You could say that we are focused on one leaf in the sense that we have identified the leaf that is vertex v, but from a grammatical point of view, it is the vertex that is definite. The concept of leaf has just been introduced, and that is not definite yet. If a tree could only have one leaf, then it would be "the". Like: "As v has no parent, it is the [definite] root of the tree." As a tree can only have one root, we use the definite article.
I've probably just taken a simple subject and made it sound very complex. :-(
Best Answer
You have an (or a) average, maximum, minimum, or other group-based calculation of something, while you take (or calculate) the average, maximum, or minimum.
Thus your samples 1, 3, and 5 are correct, but not 2, 4, or 6.
(To clarify, as per the comments: In the example sentences, the average is a property that is already known, and it is being treated grammatically in the same way as a generic, indefinite possession and thus can take the indefinite article 'a'. If the average is an unknown number that needs to be determined, then you are taking or calculating it, and then it is a specific feature and should be referred to with the definite article 'the'.)