Why is 跟他一起去不去 wrong but 跟不跟他一起去 right I am confused about the Chinese equivalent of "Do you go with him". The sentence is a so-called yes/no question by many textbooks and grammar books. Using the VA-not-VA(Verb Adjective) to compose this question, I think it should be 你跟他一起去不去？But native Chinese people say: 你跟不跟他一起去？

The "跟" is a preposition, not a verb or adjective. Why is the VA-not-VA also applicable to preposition? 

Also, why is 你跟他一起去不去 wrong?
Most Chinese prepositions are also verbs. For example:
在: to be (at) (verb), at (preposition)
跟: to follow (verb), with (preposition)
给: to give (verb), to, for (preposition)
etc.

For that reason, they do carry their verb features even when acting as prepositions. And for what I've seen since I started studying Chinese, the first verb is always the one that's negated and that's inserted in the V/A-not-V/A structure. Some examples:

你在不在中国学中文？/我不在中国学中文。
他跟不跟妈妈一起吃饭？/他不跟妈妈吃饭。
你给没给女朋友打电话？/我没给女朋友打电话。
他想不想去看电影？/他不想去看电影。
你比不比他高？/我不比他高。
你把没把书带来？/我没把书带来。
(if there are any mistakes in my examples, I'd appreciate if a native speaker could point them out)

As you can see, the "prepositions" are always negated.

You may negate other parts of the sentence, but the "neutral" negation is always negating the first verb in Chinese.

Hope this helps. Cheers