Why does adding a relationship change the display of my view?
It does not alter the markup, it just potentially reduces the result set, depending on whether the flag is set as required or not.

It depends on how you add the flag. If you add it and tick Include only flagged content, then you make the relationship required and the relevant SQL has this form:

INNER JOIN {flagging} flagging_node ON node.nid = flagging_node.entity_id AND flagging_node.fid = '1'


whereas if you add it and don't tick Include only flagged content, then the relationship is not required and the relevant SQL has this form:

LEFT JOIN {flagging} flagging_node ON node.nid = flagging_node.entity_id AND flagging_node.fid = '1'


So views alters the type of join depending on whether the relationship is required or not - INNER JOIN vs LEFT JOIN.

Look at A Visual Explanation of SQL Joins and Visual Representation of SQL Joins