The simplest way to cope with this is to define a new command for a breakable comma:
\documentclass{article}
\newcommand{\bcomma}{,\allowbreak}
\begin{document}
Figure \ref{figure:example graph} shows an example of a graph
$G = (\{v_{1}, \dots, v_{5}\},
\{(v_{1}, v_{2})\bcomma
(v_{2}, v_{3})\bcomma
(v_{1}, v_{3})\bcomma
(v_{2}, v_{5})\bcomma
(v_{3}, v_{4}),
(v_{4}, v_{5})\})$
with $|V| = n = 5$ vertices and $|E| = m = 6$ edges.
\end{document}
I'd prefer not to use \bcomma after the list of vertices and before the last edge, but in an emergency you can change also those.
A more complex solution can be written with LaTeX3 facilities:
\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\NewDocumentCommand{\mathlist}{ O{,} m m }
{
\egreg_mathlist:nnn { #1 } { #2 } { #3 }
}
\seq_new:N \l__egreg_mathlist_seq
\cs_new_protected:Npn \egreg_mathlist:nnn #1 #2 #3
{
\seq_set_split:Nnn \l__egreg_mathlist_seq { #1 } { #3 }
\seq_use:Nnnn \l__egreg_mathlist_seq { #2 } { #2 } { #2 }
}
\ExplSyntaxOff
\begin{document}
Figure \ref{figure:example graph} shows an example of a graph
$G = (\{\mathlist{,}{v_{1}, \dots, v_{5}}\},
\{\mathlist[;]{,\allowbreak}
{(v_{1}, v_{2});
(v_{2}, v_{3});
(v_{1}, v_{3});
(v_{2}, v_{5});
(v_{3}, v_{4});
(v_{4}, v_{5})}
\})$
with $|V| = n = 5$ vertices and $|E| = m = 6$ edges.
\end{document}
The \mathlist command has an optional argument (the item separator, default a comma); the first mandatory argument tells what to put in place of the separator, the second argument is the list.
The first usage of \mathlist in the example is of course redundant; the second one isn't: since the comma is used in the ordered pairs, I choose a semicolon as separator and it's substituted after processing by ,\allowbreak as in the simpler definition above.
If the list of edges is stored in a macro, the method above doesn't work. But the definition can be extended to cope with this case:
\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\NewDocumentCommand{\mathlist}{ s O{,} m m }
{
\IfBooleanTF{#1}
{ \egreg_mathlist:nnV { #2 } { #3 } #4 }
{ \egreg_mathlist:nnn { #2 } { #3 } { #4 } }
}
\seq_new:N \l__egreg_mathlist_seq
\cs_new_protected:Npn \egreg_mathlist:nnn #1 #2 #3
{
\seq_set_split:Nnn \l__egreg_mathlist_seq { #1 } { #3 }
\seq_use:Nnnn \l__egreg_mathlist_seq { #2 } { #2 } { #2 }
}
\cs_generate_variant:Nn \egreg_mathlist:nnn { nnV }
\ExplSyntaxOff
\newcommand{\edgelist}{(v_{1}, v_{2}); (v_{2}, v_{3}); (v_{1}, v_{3});
(v_{2}, v_{5}); (v_{3}, v_{4}); (v_{4}, v_{5})}
\begin{document}
Figure \ref{figure:example graph} shows an example of a graph
$G = (\{\mathlist{,}{v_{1}, \dots, v_{5}}\},
\{\mathlist[;]{,\allowbreak}
{(v_{1}, v_{2});
(v_{2}, v_{3});
(v_{1}, v_{3});
(v_{2}, v_{5});
(v_{3}, v_{4});
(v_{4}, v_{5})}
\})$
with $|V| = n = 5$ vertices and $|E| = m = 6$ edges.
The list of edges can also be obtained by
$\mathlist*[;]{,\allowbreak}{\edgelist}$.
\end{document}
I don't recommend using the following code, but it seems to do what you want: I define a command \breaktowidth where you have to specify how wide the block should be inside which line breaks are possible. Then of course \left and \right have to be used in a way such that they don't prevent the line breaks; this is done with a separate command \delimiterswithbreaks.
\documentclass[11pt,draft]{scrbook}
\usepackage{mathtools}
\newcommand{\delimiterswithbreaks}[3]{%
\mathopen{\left#1\vphantom{#3}\right.\hskip-\nulldelimiterspace}
#3
\mathclose{\hskip-\nulldelimiterspace\left.\vphantom{#3}\right#2}
}
\newcommand{\breaktowidth}[2]{\vtop{\hsize#1\noindent$#2$}}
\newcommand{\AND}[2]{\delimiterswithbreaks{(}{)}{#1\vee#2}}
\begin{document}
\begin{align*}
aaa &= \breaktowidth{6cm}{\AND{\AND{\AND{\AND{a}{b}}{\AND{\frac{a}{b}}{c}}}{\AND{\AND{\sum_a^b a}{p}}{\AND{a}{b}}}}{\AND{\AND{\AND{a}{b}}{\AND{a}{b}}}{\AND{\AND{a}{b}}{\AND{a}{b}}}}} \\
&= b
\end{align*}
\end{document}
Note: mathtools automatically loads amsmath!
Best Answer
If you need it once or twice, you can stay with something like the following. The empty
\hboxmakes sure that the following skip (\quadin this case) is not ignored.