text:
# The dynamical evolution of Taurus–Auriga-type aggregates

## 1 Introduction

Stars appear never to form in true isolation, but mostly with partners which are typically clustered into groups. These contain from a few dozen stars, such as the aggregates in the TA star formation complex (Gomez et al. 1993; Briceno et al. 2002; Hartmann 2002), through to thousands of stars in rich clusters, such as the ONC (Hillenbrand & Hartmann 1998; Muench et al. 2002) to hundreds of thousands of stars in very rich and massive young globular cluster-type assemblages. By comparing the properties of stellar populations in such different environments we learn how different physical conditions determine the star-formation products. Owing to their proximity and similar age (about 1 Myr) the stellar groups in TA and the ONC are prime candidates for detailed inter-comparisons.

Observational campaigns have established that most stars in TA are in binary systems, while in the ONC the binary properties of low-mass stars appear to be similar to those of the Galactic-field population (Duchêne 1999). Stars more massive than about $`2M_{}`$ have not formed in TA, while the ONC contains a number of O stars. The ONC has also been shown to contain many brown dwarfs (BDs) (Hillenbrand & Carpenter 2000; Muench et al. 2002), while there is a deficit of sub-stellar objects in TA (Briceno et al. 2002). Furthermore, the stellar rotation distributions in the two star-forming regions are intrinsically different (Clarke & Bouvier 2000). The two physically different systems thus appear to produce different stellar populations. However, closer inspection may indicate otherwise. Thus, massive stars cannot form in TA because the cloud cores are not massive enough. This does not necessarily imply that the stellar initial mass function (IMF) has a different form. It merely means that the most massive stars can only form if sufficient material is available. The higher frequency of binary stars in TA may be due to the TA aggregates being dynamically unevolved, given that the crossing time through an aggregate is about equal to the age of the stars or longer, while a typical star has crossed the ONC several times within its life-time. This would have reduced a TA binary frequency to the observed ONC level (Kroupa, Aarseth & Hurley 2001, hereinafter KAH), thus eroding the argument for different initial period distributions. Similarly, close encounters may have removed disk-breaking in the ONC leading to faster rotators, or there is a systematic difference in the observed stellar mass ranges in the two samples together with a mass-rotation dependence (Clarke & Bouvier 2000).

The recent affirmation by Briceno et al. (2002) that TA contains significantly fewer BDs per star than the ONC is an important clue that may indeed constitute the first direct evidence for a variation of the IMF, at least in the sub-stellar regime. The problem we are faced with in view of this empirical evidence, which implies a variation of a factor of two or so in the number of BDs per star, is that the surplus BDs detected in the ONC may be low-mass companions that have left their primaries due to encounters. This possibility, if confirmed, would again spoil the claim for a different sub-stellar IMF in TA.

To address this particular problem a number of stellar-dynamical models of embedded TA-like aggregates are calculated using the same methodology and assumptions as in a previous recent detailed study of the dynamical evolution of the ONC and the Pleiades cluster. This study by KAH finds rather excellent agreement with all available observational constraints (radial density profile, kinematics, IMF and binary properties for the ONC and the Pleiades) under a set of assumptions that define the outcome of star formation. These assumptions, which we refer to as the standard reference star-formation model (or just “standard model”), have previously been found to lead to an excellent agreement with the Galactic field population if the majority of stars form in small embedded clusters containing not more than a few hundred binaries (Kroupa 1995, hereinafter K2).

The calculations are performed with the Aarseth-Nbody6 variant GasEx described by KAH in their study of cluster formation. GasEx is a direct, high-precision $`N`$body integrator which allows accurate treatment of close encounters and multiple stellar systems in clusters through special mathematical transformation techniques of the equations of motion (regularisation). Force-softening is not implemented. It is identical to Aarseth’s Nbody6 code apart from having additional input and output features and an additional routine for setting-up a realistic initial binary-star population. GasEx also allows the inclusion of a time-varying analytic background potential to model gas expulsion form an embedded cluster, and incorporates a local Galactic-tidal field into the equations of motion of each star. A comparison of the effect of gas-expulsion on an embedded cluster using hydrodynamical computations and $`N`$body calculations assuming time-varying analytic background potentials leads to the same results (Geyer & Burkert 2001).

The purpose of this paper is to introduce the models and describe the evolution of TA–like aggregates thereby focusing attention on their BD members. Companion papers (Kroupa et al. 2003; Kroupa & Bouvier 2003) address, respectively, the (related) issues of IMF variation and binary systems in TA, and the implications this has for the origin of BDs and free-floating planetary mass objects. This paper begins with a description of the standard model (§ 2). The TA–like models studied here are introduced in § 3, and their evolution is described in § 4. The evolution of the binary systems is studied in § 5, and § 6 discusses how the relative distribution of the BDs and stars can be used to differentiate between formation models of BDs. The conclusions follow in § 7.

## 2 The standard reference star-formation model

A brief description of the standard model is presented here. It is useful as standardised and realistic initial conditions for $`N`$body computations of star clusters. The standard model is defined by a minimal set of assumptions based on empirical and theoretical evidence that describe the outcome of star formation. The model has been developed in K2 to find the dominant star-formation events that produced the Galactic field population, taking as an initial boundary condition the observed pre-main sequence binary-star properties in TA. It accounts for the properties of short-period binary systems, but does not incorporate BDs. In the strict form, it therefore only applies to late-type stars with masses in the approximate range $`0.081M_{}`$. This model leads to stellar populations in good agreement with available observational data for Galactic-field main-sequence stars and pre-main sequence stars in dense clusters including the Pleiades (K2; Kroupa, Petr & McCaughrean 1999; KAH).

The standard model can be used to search for variations of the IMF or binary-star properties in dependence of star-formation conditions. If a population is found which has an abnormal IMF or unusual binary-star properties, and if dynamical and stellar evolution cannot reproduce these observations given the standard model, then a very strong case for a variation of the IMF or binary-star properties will have been found. An example of such an application is provided by Kroupa (2001). Thus, if a modelled population is found to deviate significantly from an observed population, then this would imply that the initial conditions for that population deviate from the standard model and thus that there is a variation of the star-formation products since the standard model can reproduce a number of populations with very different ages.

We note that while the available results and notably the visualisation of pure hydrodynamical collapse computations are spectacular (Bate 2003), it is not attempted to use these results as input for the $`N`$body calculations. Feedback from the forming stars via outflows and radiation will probably significantly change the outcome of the numerical hydrodynamical experiments. These allow most of the gas to accrete, while in reality star-formation reaches an efficiency of less than 40 per cent (Lada 1999; Matzner & McKee 2000). In particular, it is noted that the modern collapse computations that lack feedback and radiative energy transport as well as magnetic forces lead to important lessons about the gravitational processes acting during the onset of star formation, but they are likely to form groups of “stars” that are too compact and therewith too dynamically violent. Stellar feedback is also likely to trigger the formation of other stars nearby, which again is not captured by the existing cloud collapse computations. It is not clear how feedback can be included in a self-consistent manner in such collapse computations, unless some parametrisation for example of the collimated outflows is attempted, and because full radiation transfer poses prohibitive challenges on the computational requirements. It is for this reason that the $`N`$body approach to young embedded clusters will remain a major work-horse in the future.

The philosophy followed here is to approach the outcome of star formation from the “other side” by studying how well-defined physical processes (mostly stellar-dynamics) affect binary-star properties and stellar distributions. Our ansatz with an analytical time-varying potential (§ 3) assumes the newly formed stars to have decoupled hydrodynamically from their gaseous environment and captures the most important physical aspect of the problem, namely the initial confinement of the stellar population in their embedded cluster (Geyer & Burkert 2001). By this approach we infer the properties the stellar distribution functions should have at the point in time when the dynamics becomes dominated by point-mass gravitational interactions, and which should ultimately come out of the cloud-collapse plus feedback work that will hopefully become available in the (distant) future.

The standard model assumes

1. All stars are paired randomly from the IMF to form binary systems with primary mass $`m_p`$ and companion or secondary mass $`m_sm_p`$.
2. The distribution of orbital elements (period, eccentricity and mass ratio) does not depend on the mass of the primary star, but allowance for eigenevolution (see below) is made.
3. Stellar masses are not correlated with the phase-space variables (no initial mass segregation in a cluster).

Assumption 1 leads to a flat initial mass-ratio distribution for late-type primaries, $`f_\mathrm{q}`$, (fig. 12 in K2; fig. 5 in Malkov & Zinnecker 2001), and is consistent with the flat mass-ratio distribution for $`qm_2/m_1\begin{array}{c}>\hfill \\ \hfill \end{array}0.2`$ derived from observational data of pre-main sequence binaries by Woitas, Leinert & Köhler (2001). They state that “these findings are in line with the assumption that for most multiple systems in T associations the components’ masses are principally determined by fragmentation during formation and not by the following accretion processes”. This in turn is supported by the finding that the mass function of pre-stellar cores in $`\rho `$ Oph already has the same shape as the Galactic-field IMF thus indicating that the fragmentation of a molecular cloud core defines the distribution of stellar masses (Motte, André & Néri 1998; Bontemps et al. 2001; Matzner & McKee 2000). The above assumptions include implicitly that any initial multiple proto-stellar systems have decayed within a few crossing times (typically $`10^4`$ yr, Reipurth 2000) to form the binary-rich initial population seen in the about 1 Myr old populations studied here.

By extending the standard model to include BDs we change the stellar pairing properties by allowing stars to have BD companions. The fraction of such systems may be appreciable but depends on the IMF for BDs. It is the purpose of the present study to investigate the consequences of the extension. Likewise, extension of the standard model to massive stars implies that most O stars will have low-mass companions, but here we are not concerned with massive stars.

Assumption 2 is posed given the indistinguishable period distribution function of Galactic-field G-dwarf, K-dwarf and M-dwarf binary systems (fig. 7 in K2). The discordant period distributions between the pre-main sequence binaries and the Galactic-field systems can be nicely explained by disruption of wide-period binaries in small embedded clusters containing a few hundred stars. This destruction process also leads to the observed mass-ratio distribution for G-dwarf primaries in the Galactic field. The model is also in good agreement with the observed smaller binary fraction of M dwarfs than of K dwarfs and G dwarfs (K2).

Assumption 3 allows investigation of the important issue whether massive stars need to form at the centres of their embedded clusters to explain the observed mass segregation in very young clusters such as the ONC (Hillenbrand 1997; Muench et al. 2003). Assumption 3 is motivated by observations which indicate that at least some massive stars appear to be surrounded by massive disks suggesting growth of the massive star by disk accretion rather than through coagulation of proto-stars (Figueredo et al. 2002; Cesaroni et al. 2003), and by the observations that forming embedded clusters are typically heavily sub-clustered, with massive stars forming at various locations (e.g. Motte, Schilke & Lis 2002). Cesaroni et al. (2003) find the massive proto-stars in the forming cluster G24.78+0.08 to lie at various locations within the central region with a radius of 0.5 pc, a region that also appears to be heavily sub-structured. On-going $`N`$body work is addressing the issue if dynamical mass-segregation can account for the observed mass segregation in the ONC for example, in which sub-structure has been erased already (Scally & Clarke 2002). Available state-of-the art work by Bonnell & Davies (1998) suggests that in the absence of initial subclustering two-body relaxation may not be able to account for the observed mass segregation. This work is based on Aarseth’s Nbody2 code which requires force softening to treat close stellar encounters, and more recent attempts with GasEx indicates that two-body relaxation may lead to the observed mass segregation if the initial configuration of the binary-rich cluster is very compact (Kroupa 2002). This topic needs to be studied in more detail. The alternative scenario is that coagulation of forming proto-stars in the densest embedded cluster region with continued accretion of low-angular momentum material onto the forming cluster core leads to the build-up of a core of massive stars there (Bonnell, Bate & Zinnecker 1998; Klessen 2001), which is tentatively supported by observational data for very young clusters and older open clusters (Raboud & Mermilliod 1998).

The initial distribution functions that are needed to describe a stellar population are the IMF, the period and eccentricity distribution functions. The IMF is conveniently (for computational purposes) taken to be a multi-power-law form,

$$\xi (m)=k\{\begin{array}{cc}\left(\frac{m}{m_\mathrm{H}}\right)^{\alpha _0},\hfill & m_l<mm_\mathrm{H},\hfill \\ \left(\frac{m}{m_\mathrm{H}}\right)^{\alpha _1},\hfill & m_\mathrm{H}<mm_0,\hfill \\ \left[\left(\frac{m_0}{m_\mathrm{H}}\right)^{\alpha _1}\right]\left(\frac{m}{m_0}\right)^{\alpha _2},\hfill & m_0<mm_1,\hfill \\ \left[\left(\frac{m_0}{m_\mathrm{H}}\right)^{\alpha _1}\left(\frac{m_1}{m_0}\right)^{\alpha _2}\right]\left(\frac{m}{m_1}\right)^{\alpha _3},\hfill & m_1<mm_2,\hfill \\ \left[\left(\frac{m_0}{m_\mathrm{H}}\right)^{\alpha _1}\left(\frac{m_1}{m_0}\right)^{\alpha _2}\left(\frac{m_2}{m_1}\right)^{\alpha _3}\right]\left(\frac{m}{m_2}\right)^{\alpha _4},\hfill & m_2<mm_u,\hfill \end{array}$$
(1)
where $`k`$ contains the desired scaling, and $`dN=\xi (m)dm`$ is the number of stars in the mass interval $`m`$ to $`m+dm`$. Eq. 1 is the general form of a five-part power-law form, but at present observations only support a three-part power-law IMF (Kroupa 2002) with $`m_l=0.01M_{},m_\mathrm{H}=0.08M_{},m_0=0.5M_{}`$, and $`\alpha _2=\alpha _3=\alpha _4`$,

$$\begin{array}{cc}\alpha _0=+0.3\pm 0.7,\hfill & 0.01m/M_{}<0.08,\hfill \\ \alpha _1=+1.3\pm 0.5,\hfill & 0.08m/M_{}<0.50,\hfill \\ \alpha _2=+2.3\pm 0.3,\hfill & 0.50m/M_{}.\hfill \end{array}$$
(2)
The multi-part power-law form is convenient because it allows an analytic mass-generation function to be used which leads to very efficient generation of masses from an ensemble of random deviates. The multi-part power-law form also has the significant advantage that various parts of the IMF can be changed without affecting other parts, such as changing the number of massive stars by varying $`\alpha _4`$ without affecting the form of the luminosity function of low-mass stars. Other functional descriptions of the IMF are in use (e.g. Chabrier 2001).

The initial period distribution function needs to be consistent with the TA data, and a convenient form which also has an analytic period-generation function is derived in K2,

$$f_{\mathrm{P},\mathrm{birth}}=2.5\frac{\left(lP1\right)}{45+\left(lP1\right)^2},$$
(3)
where $`f_{\mathrm{P},\mathrm{birth}}dlP`$ is the proportion of binaries among all systems with periods in the range $`lP`$ to $`lP+dlP`$ ($`P`$ in days throughout this paper), and $`1lP\mathrm{log}_{10}P`$. The usual notation for the binary proportion is used here, $`f_\mathrm{P}=N_{\mathrm{bin},\mathrm{P}}/N_{\mathrm{sys}}`$, where $`N_{\mathrm{sys}}=N_{\mathrm{bin}}+N_{\mathrm{sing}}`$ is the number of systems and $`N_{\mathrm{bin},\mathrm{P}}`$ is the number of binary systems with periods in the bin $`lP`$. The condition $`_{lP}f_{\mathrm{P},\mathrm{birth}}𝑑lP=1`$ (all stars being born in binaries) gives $`P_{\mathrm{max}}=10^{8.43}`$ d for the maximum period obtained from the distribution 3. $`N`$body experiments demonstrate that the observed range of periods ($`P10^{09}`$ d) must be present as a result of the star-formation process; encounters in very dense sub-groups cannot sufficiently widen initially more restricted period distributions and at the same time lead to the observed fraction of binaries in the Galactic field (Kroupa & Burkert 2001). Observations show that the eccentricity distribution of Galactic-field binary systems is approximately thermal, $`f_\mathrm{e}=2e`$, and $`N`$body calculations demonstrate that such a distribution must be primordial because encounters of young binaries in their embedded clusters cannot thermalize an initially different distribution (K2; Kroupa & Burkert 2001).

Binary systems in the Galactic field with short periods ($`P\begin{array}{c}<\hfill \\ \hfill \end{array}10^3`$ d) do show departures from simple pairing by having a bell-shaped eccentricity distribution and a mass-ratio distribution that appears to deviate from random sampling from the IMF. This is apparent most dramatically in the eccentricity–period diagram which shows an upper eccentricity-envelope for short-period binaries (Duquennoy & Mayor 1991). This indicates that binary-system–internal processes may have evolved a primordial distribution. Such processes are envelope–envelope or disk–disk interactions during youth, shared accretion during youth, rapid tidal circularisation during youth, and slow tidal circularisation during the main-sequence phase. These system-internal processes that change the orbital parameters cannot be expressed with only a few equations given the extremely complex physics involved, but a simple analytical description is available through the K2-formulation of eigenevolution–feeding. Feeding allows the mass of the secondary to grow, while eigenevolution allows the eccentricity to circularise and the period to decrease at small peri-astron distances, and merging to occur if the semi-major axis of the orbit is smaller than 10 Solar radii. About 3 per cent of initial binaries merge to form a single star. The eigenevolved model-main-sequence eccentricity–period diagram, and the eccentricity and mass-ratio distributions of short-period systems, agree well with observational data. In particular, although the minimum period obtained from eq. 3 is $`P=10`$ d, eigenevolution leads to the correct number of $`P<10`$ d periods. The resulting IMF of all stars shows slight departures from the input IMF (eq. 2) as a result of the mass-growth (feeding) of some secondaries, but the deviations are well within the IMF uncertainties.

## 3 Models of Taurus–Auriga-like aggregates

A star-formation event produces a spatial distribution of stars which is typically centrally concentrated. As a first approach, this density distribution is assumed to be smooth without sub-structure, because this minimises the number of parameters needed. Each binary system is thus provided with phase-space variables which define its initial location and velocity relative to the other binaries. A mathematically very convenient smooth spatial distribution function is given by the Plummer model,

$$\rho (R)=\frac{3N_{\mathrm{bin}}}{4\pi R_{\mathrm{pl}}^3}\frac{1}{[1+(R/R_{\mathrm{pl}})^2]^{5/2}},$$
(4)
where $`N_{\mathrm{bin}}`$ is the number of binary systems in the aggregate or cluster, and $`R_{0.5}=1.305R_{\mathrm{pl}}`$ is the half-mass radius. For each position the associated velocity needs to satisfy Poisson’s equation; the generating functions for position and velocity variables are presented in Aarseth, Hénon & Wielen (1974).

To study the dynamical evolution of TA-like aggregates 25 binaries are distributed as a Plummer density distribution embedded in an analytical background gas potential with the same $`R_{0.5}`$ as the stars, but twice the stellar mass. The star-formation efficiency in the aggregate is thus assumed to be $`33`$ per cent ($`ϵ=0.33`$; Lada 1999). The velocity of each binary-star centre-of-mass is $`v_{\mathrm{bin},\mathrm{g}}=v_{\mathrm{bin}}/\sqrt{ϵ}`$ to insure initial dynamical equilibrium, where $`v_{\mathrm{bin}}`$ is the velocity in an equilibrium aggregate without gas. Assuming dynamical equilibrium is equivalent to assuming that the stars form from condensations in a cloud core in virial equilibrium. The gas potential is kept constant for a time $`\tau _\mathrm{D}`$ after which it begins to evolve on an exponential time-scale $`\tau _\mathrm{M}`$. Different values for $`\tau _\mathrm{D}`$ and $`\tau _\mathrm{M}`$ test the effect on the binary population of having the aggregates embedded in the potential for time scales ranging from a fraction to about two crossing times. Each model is integrated for 40 Myr, by which time the aggregates have largely dissolved. All stars and binaries are kept in memory for data reduction, for which a separate software package has been written. Briefly, GasEx writes out snapshots of all data at regular time intervals. These are used to find all bound binary systems and single stars and other data relevant for the present discussion. We note that a more self-consistent treatment of gas-expulsion using the smooth-particle-hydrodynamics approximation to model the gas dynamics leads to the same results as when applying a time-varying analytical background potential (Geyer & Burkert 2001).

The models are listed in Table 1. The half-mass radii and number of systems are chosen to reflect the observed values (Gomez et al. 1993; Hartmann, Ballesteros-Paredes & Bergin 2001; Briceno et al. 2002; Palla & Stahler 2002). The durations of the embedded phase ($`t_\mathrm{D}+2\tau _\mathrm{M}`$) approximately span the duration of star formation and is typically longer than the crossing time – the residual gas is removed over time through the accumulating stellar outflows (Matzner & McKee 2000). There are 140 renditions per model with different initial random number seeds. The IMF power-law index in the BD mass range, $`\alpha _0`$, is changed between some of the models to allow an investigation of various BD contents. The table also contains the two KAH models of dense and rich ONC-type clusters. These models are constructed in exactly the same way as the present TA-like models, and thus allow a consistent comparison of the evolution of the binary population and the apparent IMF with empirical data to test for possible deviations from the standard model.

## 4 Dynamical evolution

An outline of the dynamical evolution and associated changes of the stellar population is given in this section.

The aggregates evolve by expanding due to two-body encounters and the removal of the gas. Snapshots of this are shown in Figs 1 and 2. The density profiles of stellar- and BD-systems are plotted at various times in Figs. 3 (model T0) and 4 (model T5). The dissolution of the aggregates is evident by the reduction with time of the number densities, and the figure also shows that the BD and stellar populations do not separate significantly in these models. That is, the BDs trace the stars, except for a small high-velocity BD distribution which results from BDs being ejected in binary–binary encounters (Figs. 16 and 17 below).

The nominal dissolution time due to redistribution of energy within the aggregates due to two-body encounters is $`t_{\mathrm{diss}}100t_{\mathrm{relax}}`$, where $`t_{\mathrm{relax}}0.1Nt_{\mathrm{cross}}/\mathrm{ln}N`$ is the median two-body relaxation time (Binney & Tremaine 1987). For models T0-T5 $`t_{\mathrm{relax}}0.81.3`$ Myr for $`N_{\mathrm{sys}}=2550`$, so that $`t_{\mathrm{diss}}80130`$ Myr. Gas removal unbinds the aggregates on a much shorter time-scale though, as is shown in Figs 5 and 6. Thus, by 32 Myr models T0, T1, T2 and T5 contain on average only about 2, 5, 7 and 7 systems within the central 1 pc sphere, respectively.

The number of BD systems within the central 1 pc sphere increases at first as a result of BD companions being freed from binary systems, but at later times ($`t\begin{array}{c}>\hfill \\ \hfill \end{array}5`$ Myr) the relative number of BDs decays more rapidly than the number of stellar systems as a result of energy equipartition in the aggregates and gas removal (Fig. 7). During the embedded phase the BDs acquire on average somewhat higher velocities than the stars leading to their slightly more rapid dispersal after the gas has been removed (§ 6). The net effect is nevertheless such that at 0, 1 and about 15 Myr the BD- and stellar-systems have statistically indistinguishable density profiles (Figs 3 and 4).

The core radius (eq. 11 in KAH), which indicates that radius by which the luminosity density has fallen to half its central value, is shown in Fig. 8. It expands substantially and becomes larger than 1 pc by 6–8 Myrs for models T0 and T1. The slowed expansion due to delayed gas-expulsion in models T2–T5 is evident in Fig. 9, these models retain a more compact morphology and the core radius reaches 1 pc by about 20 Myr.

The evolution of the three-dimensional velocity dispersion within the central 1 pc sphere is shown in Figs. 10 and 11. It drops from an initial 0.6 km/s (models T0, T2–T5) or 0.4 km/s (model T1) to values close to 0.3 km/s or less. These values are consistent with the low stellar velocity dispersion of 0.2 km/s (one dimensional) suggested within the TA cloud filaments by Hartmann (2002).

The mean system mass within the central 1 pc region indicates the level to which mass segregation develops. It increases only by a small amount in all models (Figs. 12, 13). By about 32 Myr models T0 and T2–T5 have a mean system mass of $`0.390.45M_{}`$, while the initially least concentrated model T1 (which has the same IMF as T0) has $`<m>0.25M_{}`$. Thus, initially more compact aggregates produce final long-lived small$`N`$ groups with more massive components, which is a result of the larger probability of partner exchanges in the denser environment.

## 5 The binary systems

The binary-star population evolves through system-internal processes (eigenevolution, § 2). This affects only the short-period binaries ($`P\begin{array}{c}<\hfill \\ \hfill \end{array}10^3`$ d). Encounters between binaries disrupt long-period binaries on the crossing time-scale of the aggregate. Binary-system disruption extends approximately down to a characteristic (or “thermal”) period, $`P_{\mathrm{th}}`$ \[d\], at which the circular orbital velocity, $`v_{\mathrm{orb}}`$ \[km/s\], of a binary system with mass $`m_{\mathrm{sys}}`$ \[$`M_{}`$\], equals the velocity dispersion, $`\sigma _{3\mathrm{D}}`$ \[km/s\], in the cluster. Because $`\sigma _{3\mathrm{D}}`$ decreases as the aggregate expands, $`P_{\mathrm{th}}`$ moves to longer periods until it extends beyond the cutoff period of the evolving period distribution function, which is moving towards $`P_{\mathrm{th}}`$ (Kroupa 2000). There is not a sharp truncation of the period distribution function however — binaries with $`P>P_{\mathrm{th}}`$ located in the outer region of the cluster at $`t=0`$ may arrive in the inner parts of the cluster when $`P<P_{\mathrm{th}}`$ making them resistant against disruption. When the crossover of $`P_{\mathrm{th}}`$ and $`P_{\mathrm{cut}}`$ happens, further binary-disruption is mostly halted, and only rare close encounters in the surviving stellar group lead to further changes in the orbital parameters of a few binaries. With

$$\mathrm{log}_{10}P=6.986+\mathrm{log}_{10}m_{\mathrm{sys}}3\mathrm{log}_{10}v_{\mathrm{orb}},$$
(5)
$`P=P_{\mathrm{th}}`$ if $`v_{\mathrm{orb}}=\sigma _{3\mathrm{D}}`$. For $`\sigma _{3\mathrm{D}}=0.6`$ km/s and $`m_{\mathrm{sys}}=0.4M_{}`$ (Table 1) $`P_{\mathrm{th}}=10^{7.3}`$ d, which means that a large number of binaries with periods $`7.3\begin{array}{c}<\hfill \\ \hfill \end{array}lP\begin{array}{c}<\hfill \\ \hfill \end{array}8.3`$ will be disrupted implying reduction of $`f_\mathrm{P}`$ by about 20 per cent. The final binary-fraction should thus be $`f0.8`$. This is confirmed by the data plotted in Figs. 14 and 15, which also confirm that prior dynamical evolution of the present-day TA groups did not lead to significant changes of the binary-star population. The figures show that BDs retain a significantly smaller binary proportion than stellar primaries. This is a result of the weaker binding energy of BD–BD binaries. Fig. 15 also shows that models T2 and T5 have a significantly smaller BD binary proportion than models T0 and T1. This comes about because models T2–T5 enjoy a longer embedded phase leading to more encounters per system. An effect also playing a role is that T2–T5 have relatively fewer BDs by virtue of the steeply declining IMF for $`m<0.08M_{}`$. A larger fraction of stars is thus obtained implying a larger average mass of the siblings that a typical BD binary encounters, and thus larger relative perturbative forces which are more efficient in destroying the BD binaries than in models T0 and T1.

The evolution of the binary proportion of the ONC-like models of KAH is also plotted in Fig. 14. From Table 1, $`\sigma _{3\mathrm{D}}=6.8`$ (model A) and 10.8 (model B), implying $`P_{\mathrm{th}}=10^{4.1}`$ d (model A) and $`10^{3.5}`$ d. Thus, in ONC-like clusters the period distribution function is cut-off at a much shorter period than in TA-like aggregates despite the same initial period distribution.

To summarize, the important result here is that TA-like aggregates could not have provided significantly to the Galactic-field population which has a binary proportion of about $`f=0.550.6`$ (Duquennoy & Mayor 1991).

## 6 The relative distribution of brown dwarfs and stars

The relative distribution of stars and BDs is a potential discriminant between different formation scenarios. For example, the embryo-ejection hypothesis according to which BDs are ejected unfinished stars from forming multiple systems (Reipurth 2000; Boss 2001; Reipurth & Clarke 2001; Bate, Bonnell & Bromm 2002) implies a spatially wide distribution of BDs if their typical ejection velocities are about 1 km/s or larger.

In contrast, the standard reference star-formation model (§ 2), which is extended here and in KAH to include BDs, assumes that stars and BDs form with the same kinematical and binary properties at the point when the system can be treated as an $`N`$body system. For TA-like aggregates the standard model with BDs implies that the BDs and stars trace approximately the same density distribution (Figs. 3 and 4). Close encounters between binaries eject, from the temporary four and later three-body system, preferentially the least massive members, i.e. typically the BDs (Sterzik & Durisen 1998). The standard model should thus yield, for the BDs, a high-velocity tail populated almost exclusively by single BDs. This is evident in Figs. 3 and 4 by the slightly increasing ratio $`\rho _{\mathrm{BD}}/\rho _{\mathrm{st}}`$ with increasing $`r`$ at late times. The ejected BDs will also have truncated disks with a truncation radius of about the peri-astron distance that produced the BD escaper. Thus, for an ejection velocity $`1`$ km/s the truncation radius will be $`40`$ AU (eq. 5 plus Kepler’s third law).

This is basically the same result as for the embryo-ejection scenario (Reipurth 2000) which was recently championed by Reipurth & Clarke (2001), making a distinction between both (standard model vs the ejection hypothesis for the origin of BDs) rather difficult if the evidence is based only on a distributed, binary-deficient BD population which also has truncated disks when young. It is thus essential to use the entire information, namely the binary properties in dependence of the locations and velocities of the BD population. Thus, the embryo-ejection hypothesis implies a shallow density distribution of mostly single BDs extending to large distances, while the standard model implies a density distribution which is similar to that of the stars with an extended low-density tail of mostly single BDs. The fraction of BDs per star as a function of distance from the aggregate centre (Figs 3, 4) is thus an observational diagnostic that should help distinguishing the two models.

The velocity distribution functions are quantified in Figs. 16 and 17 for models T0 and T5, respectively (the other models T2-T4 yield very similar results, while model T1 has a narrower velocity distribution and a much smaller ejection tail). Model T5 enjoys a longer embedded phase which leads to a more pronounced high-velocity tail for BDs, since the system remains in a more compact configuration for a longer time allowing more encounters than in model T0.

By about 15 Myr about 15 per cent of all BD systems have a velocity larger than 1 km/s in both models. The final stellar velocity distribution is centred on smaller velocities in T5 than in model T0. This results from the slower gas-removal allowing the stellar orbits to adjust more to the changing conditions than in model T0 (T5 is more adiabatic than T0), while the BD population has more time to be accelerated to higher velocities on average by the encounters with the stellar members. Effectively, models T5 (and T2–T4) thus lead to a more pronounced kinematical separation between stars and BDs. This effect will, however, be difficult to observe for any individual aggregate because of the small number of systems per aggregate (see Figs. 1 and 2).

The figures also show the binary proportion as a function of velocity. The ejected BDs have a low if not negligible binary proportion (as for the embryo-ejection hypothesis), and their binary proportion is systematically smaller in the velocity interval 0.4–1 km/s than that of stellar primaries. The standard model with BDs implies that the BDs retain a high binary proportion for $`v\begin{array}{c}<\hfill \\ \hfill \end{array}0.6`$ km/s. Such BDs are spatially distributed similarly to the stars. This last point is an important observable diagnostic distinguishing the embryo-ejection hypothesis from the standard model with BDs, given that the likelihood for ejection of two embryos that become a binary BD is exceedingly small.

## 7 Concluding remarks

The dynamical evolution of Taurus–Auriga-like populations is studied using high-precision $`N`$body computations of embedded aggregates of 25 binaries with different initial concentrations. The aggregates remove their gas on time-scales of a fraction to a few crossing times. The standard model (random pairing from the IMF, no correlation between binary-star orbital parameters and primary mass, and no initial mass segregation) is used to define the input population.

The aggregates disperse within about 10 Myr leaving a population that is dynamically largely unevolved. In particular, the binary population remains high with $`f>0.8`$. This shows that for the initial conditions chosen for the aggregates, the binary destruction by $`N`$body processes is minor and leaves a population that is rich in binaries as that observed. Taurus–Auriga-type star formation can therefore be only a minor contributor to the Galactic field population which has $`f=0.550.6`$.

The distributed BD population has a negligible binary proportion and truncated disks, as a result of this population component being preferably ejected during binary–binary encounters from the aggregates. This makes it difficult to empirically verify the hypothesis that BDs may originate as ejected unfinished stellar embryos from few-body systems using the binary proportion, disk truncation and wide spatial distribution of BDs as sole evidence. However, according to the standard model used here (i.e. BDs form with the same kinematical, spatial and binary properties as stars), slow BDs which also share a similar spatial distribution as the stars retain a high binary proportion. This is a powerful distinguishing diagnostic from the embryo-ejection hypothesis, because the slow-moving population is much easier to find given that it overlaps the stellar distribution.

The computations presented here focus on T-A aggregates, but are equally applicable to other young low-mass populations. For example, Chauvin et al. (2002) find the $`\begin{array}{c}<\hfill \\ \hfill \end{array}5`$ Myr old MBM12 association to have an excess binary fraction over Galactic field G and M dwarfs. This may be explainable through an origin of the MBM12 stars in low-mass aggregates similar to T-A.

## acknowledgements

We thank Gaspard Duchêne and Estelle Moraux for useful discussions. PK thanks the staff of the Observatoire de Grenoble for their very kind hospitality and the Université Joseph Fourier for supporting a very enjoyable and productive stay during the summer of 2002.


format: text

text:
# NONSTANDARD GRAPHS, REVISED

Abstract — This is a revision of the paper archived previously on August 22, 2002. It corrects a mistake in Sec. 8 concerning eccentricities of graphs.

From any given sequence of finite or infinite graphs, a nonstandard graph is constructed. The procedure is similar to an ultrapower construction of an internal set from a sequence of subsets of the real line, but now the individual entities are the vertices of the graphs instead of real numbers. The transfer principle is then invoked to extend several graph-theoretic results to the nonstandard case. After incidences and adjacencies between nonstandard vertices and edges are defined, several formulas regarding numbers of vertices and edges, and nonstandard versions of Eulerian graphs, Hamiltonian graphs, and a coloring theorem are established for these nonstandard graphs.

Key Words: Nonstandard graphs, transfer principle, ultrapower constructions.

1. Introduction

In the book  (se Sec. 19.1), R. Goldblatt obtained a nonstandard graph $`^{}V,^{}E`$ as an enlargement of a conventional graph $`V,E`$ defined as a set $`V`$ of vertices and a set $`E`$ of edges determined by a symmetric irreflexive relationship of $`V`$. The transfer principle was then used to establish in a nonstandard way the standard theorem that, if every finite subgraph of a conventional infinite graph $`G`$ has a coloring with finitely many colors, then $`G`$ itself has such a finite coloring.

On the other hand, in several recent works (see , , and the references therein), the idea of nonstandard transfinite graphs and networks was introduced and investigated. The basic idea in those works was to start with a given transfinite graph, to reduce it to a finite graph by shorting and opening edges, and then to obtain an expanding sequence of finite graphs by restoring edges sequentially. If all this is done in an appropriate fashion, it may happen that the sequence of finite graphs fills out and restores the original transfinite graph once the restoration process is completed. If in addition there is an assignment of electrical parameters to the edges, the final result may be sequences of edge currents and edge voltages, from which nonstandard hyperreal currents and voltages can be derived. The latter hyperreal quantities will then automatically satisfy Kirchhoff’s laws, even though Kirchhoff’s laws may on occasion be violated in the original transfinite network when standard real numbers are used—an important advantage of this nonstandard approach.

However, this is only a partial construction of a nonstandard graph in the sense that the completion of the restoration process—if successful—results in the original standard transfinite graph. The sequence of restorations only provides a means of constructing hyperreal currents and voltages satisfying Kirchhoff’s laws. Another approach might start with an arbitrary sequence of conventional (finite or infinite) graphs and construct from that a nonstandard graph in much the same way as an internal set in the hyperreal line $`{}_{}{}^{}IR`$ is constructed from a given sequence of subsets of the real line $`IR`$, that is, by means of an ultrapower construction \[5, page 36\]. In this case, the resulting nonstandard graph has nonstandard edges and nonstandard vertices, and it thereby is much different from those of the prior works , . Also, the present approach differs from Goldblatt’s result in that the graphs of the sequence need not be vertex-induced subgraphs of a given graph.

Our objective in this work is to develop this latter approach to nonstandard graphs. The individual elements are chosen to be the vertices of the graphs along with all the natural numbers. These individuals are not sets by assumption and therefore have no members. All the other standard and nonstandard entities are derived from these individuals. For example, an edge is defined to be a pair of vertices, which is one of the conventional ways of defining a graph. Then, certain equivalence classes of sequences of standard vertices are defined to be nonstandard vertices, and these then yield nonstandard edges as certain equivalence classes of sequences of standard edges. In this approach, there are no multiedges (i.e., no parallel edges) and no self-loops (i.e., no edge consisting of just a single vertex).

After setting up our nonstandard graphs using an ultrapower approach, we invoke the transfer principle to lift several standard graph-theoretic results into a nonstandard setting. For example, the relationship between the number of vertices, the number of edges, and the cyclomatic number of a standard finite connected graph continues to hold for nonstandard graphs except that these numbers are replaced by hypernatural numbers. Similarly, standard theorems concerning Eulerian graphs, Hamiltonian graphs, and a coloring theorem are also extended to the nonstandard setting. By virtue of the transfer principle, this only requires that the standard theorems be stated as sentences in symbolic logic, which are then transferred to appropriate sentences for nonstandard graphs.

In the following, $`|A|`$ will denote the cardinality of a set $`A`$. Also, $`IN=\{0,1,2,\mathrm{}\}`$ is the set of all natural numbers, and $`IR`$ is the set of real numbers. Thus, $`{}_{}{}^{}IN`$ is the set of hypernaturals, and $`{}_{}{}^{}IR`$ is the set of hyperreals.

2.Nonstandard Graphs

A standard graph $`G`$ is a conventional (finite or infinite) graph $`G=\{X,B\}`$, where $`X`$ is the set of its vertices and $`B`$ is the set of its edges. Each edge $`bB`$ is a two-element set $`b=\{x,y\}`$ with $`x,yX`$ and $`xy`$; $`b`$ and $`x`$ are said to be incident and so, too, are $`b`$ and $`y`$. Also, $`x`$ and $`y`$ are said to be adjacent through $`b`$.

Next, let $`G_n:nIN`$ be a given sequence of graphs. For each $`n`$, we have $`G_n=\{X_n,B_n\}`$, where $`X_n`$ is the set of edges and $`B_n`$ is the set of vertices. We allow $`X_nX_m\mathrm{}`$ so that $`G_n`$ and $`G_m`$ may be subgraphs of a larger graph. In fact, we may have $`X_n=X_m`$ and $`B_n=B_m`$ for all $`n,mIN`$ so that $`G_n`$ may be the same graph for all $`nIN`$. Furthermore, let $``$ be a chosen nonprincipal ultrafilter on $`IN`$ \[5, pages 18-19\].

In the following, $`x_n=x_n:nIN`$ will denote a sequence of vertices with $`x_nX_n`$ for all $`nIN`$. A nonstandard vertex $`{}_{}{}^{}x`$ is an equivalence class of such sequences of vertices, where two such sequences $`x_n`$ and $`y_n`$ are taken to be equivalent if $`\{n:x_n=y_n\}`$, in which case we write “$`x_n=y_n`$ a.e.” or say that $`x_n=y_n`$ “for almost all $`n`$.” We also write $`{}_{}{}^{}x=[x_n]`$, where it is understood that the $`x_n`$ are the members of any one sequence in the equivalence class.

That this truly defines an equivalence class can be shown as follows. Reflexivity and symmetry being obvious, consider transitivity: Given that $`x_n=y_n`$ a.e. and that $`y_n=z_n`$ a.e., we have $`N_{xy}=\{n:x_n=y_n\}`$ and $`N_{yz}=\{n:y_n=z_n\}`$. By the properties of the ultrafilter, $`N_{xy}N_{yz}`$. Moreover, $`N_{xz}=\{n:x_n=z_n\}(N_{xy}N_{yz})`$. Therefore, $`N_{xz}`$. Hence, $`x_n=z_n`$ a.e.; transitivity holds. We let $`{}_{}{}^{}X`$ denote the set of nonstandard vertices.

Next, we define the nonstandard edges: Let $`{}_{}{}^{}x=[x_n]`$ and $`{}_{}{}^{}y=[y_n]`$ be two nonstandard vertices. This time, let $`N_{xy}=\{n:\{x_n,y_n\}B_n\}`$ and $`N_{xy}^c=\{n:\{x_n,y_n\}B_n\}`$. Since $``$ is an ultrafilter, exactly one of $`N_{xy}`$ and $`N_{xy}^c`$ is a member of $``$. If it is $`N_{xy}`$, then $`{}_{}{}^{}b=[\{x_n,y_n\}]`$ is defined to be a nonstandard edge; that is, $`{}_{}{}^{}b`$ is an equivalence class of sequences $`b_n`$ of edges $`b_n=\{x_n,y_n\}B_n`$, $`n=0,1,2,\mathrm{}`$. In this case, we also write $`{}_{}{}^{}x,^{}y^{}b`$ and $`{}_{}{}^{}b=\{^{}x,^{}y\}`$. We let $`{}_{}{}^{}B`$ denote the set of nonstandard edges. On the other hand, if $`N_{xy}^c`$, then $`[\{x_n,y_n\}]`$ is not a nonstandard edge.

We shall now show that this definition is independent of the representatives chosen for the vertices. Let $`[\{x_n,y_n\}]`$ and $`[\{v_n,w_n\}]`$ represent the same nonstandard edge. We want to show that, if $`x_n=v_n`$ a.e., then $`y_n=w_n`$ a.e. Suppose $`y_nw_n`$ a.e. Then, $`\{n:x_n=v_n\}\{n:y_nw_n\}`$. Thus, there is at least one $`n`$ for which the three vertices $`x_n=v_n`$, $`y_n`$, and $`w_n`$ are all incident to the same standard edge—in violation of the definition of a edge. Similarly, if all of $`x_n`$, $`y_n`$, $`v_n`$, $`w_n`$ are different a.e., then there would be a standard edge having four incident vertices—again a violation.

Next, we show that we truly have an equivalence relationship for the set of all sequences of standard edges. Reflexivity and symmetry being obvious again, consider transitivity: Let $`{}_{}{}^{}b=[\{x_n,y_n\}]`$, $`{}_{}{}^{}\stackrel{~}{b}=[\{\stackrel{~}{x}_n,\stackrel{~}{y}_n\}]`$, $`{}_{}{}^{}\stackrel{´}{b}=[\{\stackrel{´}{x}_n,\stackrel{´}{y}_n\}]`$, and assume that $`{}_{}{}^{}b=^{}\stackrel{~}{b}`$ and $`{}_{}{}^{}\stackrel{~}{b}=^{}\stackrel{´}{b}`$. We want to show that $`{}_{}{}^{}b=^{}\stackrel{´}{b}`$. We have $`N_{b\stackrel{~}{b}}=\{n:\{x_n,y_n\}=\{\stackrel{~}{x}_n,\stackrel{~}{y}_n\}\}`$ and $`N_{\stackrel{~}{b}\stackrel{´}{b}}=\{n:\{\stackrel{~}{x}_n,\stackrel{~}{y}_n\}=\{\stackrel{´}{x}_n,\stackrel{´}{y}_n\}\}`$. Moreover, $`N_{b\stackrel{´}{b}}=\{n:\{x_n,y_n\}=\{\stackrel{´}{x}_n,\stackrel{´}{y}_n\}\}(N_{b\stackrel{~}{b}}N_{\stackrel{~}{b}\stackrel{´}{b}})`$. Therefore, $`N_{b\stackrel{´}{b}}`$. Thus, $`{}_{}{}^{}b=^{}\stackrel{´}{b}`$, as desired.

Finally, we define a nonstandard graph $`{}_{}{}^{}G`$ to be the pair $`{}_{}{}^{}G=\{^{}X,^{}B\}`$.

Let us now take note of a special case that arises when all the $`G_n`$ are the same standard graph $`G=\{X,B\}`$. In this case, we call $`{}_{}{}^{}G=\{^{}X,^{}B\}`$ an enlargement of $`G`$, in conformity with an “enlargement” $`{}_{}{}^{}A`$ of a subset $`A`$ of $`IR`$ \[5, pages 28-29\]. If in addition $`G`$ is a finite graph, each vertex $`x^{}X`$ can be identified with a vertex of $`X`$ because the enlargement of a finite set equals the set itself. Similarly, every branch $`b^{}B`$ can be identified with a branch in $`B`$. In short, $`{}_{}{}^{}G=G`$. On the other hand, if $`G`$ is a conventionally infinite graph, $`X`$ is an infinite set and its enlargement $`{}_{}{}^{}X`$ has more elements, namely, nonstandard vertices that are not equal to standard vertices, (i.e., $`{}_{}{}^{}XX`$ is not empty). Similarly, $`{}_{}{}^{}BB`$ is not empty too. In short, $`{}_{}{}^{}G`$ is a proper enlargement of $`G`$.

Example 2.1. Let $`G`$ be a one-way infinite path $`P`$:

$$P=x_0,b_0,x_1,b_1,x_2,b_2,\mathrm{}$$

Also, let $`G_n=G`$ for all $`nIN`$, and let $`{}_{}{}^{}G=[G_n]=\{^{}X,^{}B\}`$. Next, let $`k_n:nIN`$ be any sequence of natural numbers, and set $`{}_{}{}^{}x=[x_{k_n}]`$ and $`{}_{}{}^{}y=[x_{k_n+1}]`$. Then, $`{}_{}{}^{}x`$ and $`{}_{}{}^{}y`$ are two vertices in the enlargement $`{}_{}{}^{}G`$ of $`G`$, and $`{}_{}{}^{}b=\{^{}x,^{}y\}=[\{x_{k_n},x_{k_n+1}\}]`$ is an edge in $`{}_{}{}^{}G`$. On the other hand, if $`m_n:nIN`$ is another sequence of natural numbers with $`m_n>1`$, then $`{}_{}{}^{}z=[x_{k_n+m_n}]`$ is another nonstandard vertex in $`{}_{}{}^{}G`$ different from $`{}_{}{}^{}x`$ and $`{}_{}{}^{}y`$ and appearing after $`{}_{}{}^{}y`$ in the enlarged path. Moreover, $`[\{x_{k_n},x_{k_n+m_n}\}]`$ is not a nonstandard edge. In this way, no vertex or edge repeats in the enlarged path. $`\mathrm{}`$

Another special case arises when almost all the $`G_n`$ are (possibly different) finite graphs. Again in conformity with the terminology used for hyperfinite internal subsets of $`{}_{}{}^{}R`$ \[5, page 149\], we will refer to the resulting nonstandard graph $`{}_{}{}^{}G`$ as a hyperfinite graph.111This should not be confused with a hypergraph—an entirely different object . As a result, we can lift many theorems concerning finite graphs to hyperfinite graphs. It is just a matter of writing the standard theorem in an appropriate form using symbolic logic and then applying the transfer principle. We let $`{}_{}{}^{}G_{f}^{}`$ denote the set of hyperfinite graphs.

3. Incidences and Adjacencies between Vertices and Edges

Let us now define these ideas for nonstandard graphs both in terms of an ultrapower construction and by transfer of appropriate symbolic sentences. In the subsequent sections, we will usually confine ourselves to the transfer principle. We henceforth drop the asterisks when denoting nonstandard vertices and edges. These are specified as members of $`{}_{}{}^{}X`$ and $`{}_{}{}^{}B`$ respectively.

Incidence between a vertex and an edge: Given a sequence $`G_n:nIN`$ of standard graphs $`G_n=\{X_n,B_n\}`$, a nonstandard vertex $`x=[x_n]^{}X`$ and a nonstandard edge $`b=[b_n]^{}B`$ are said to be incident if $`\{n:x_nb_n\}`$, where as always the nonprincipal ultrafilter $``$ is understood to be chosen and fixed.

On the other hand, we can define incidence between a standard vertex $`xX`$ and a standard edge $`bB`$ for the graph $`G=\{X,B\}`$ through the symbolic sentence

$$(xX)(bB)(xb)$$

By transfer, we have that $`x^{}X`$ and $`b^{}B`$ are incident when the following sentence is true.

$$(x^{}X)(b^{}B)(xb)$$

These are equivalent definitions.

Adjacency between vertices: For a standard graph $`G=\{X,B\}`$, two vertices $`x,yX`$ are called adjacent and we write $`xy`$ if the following sentence on the right-hand side of $``$ is true.

$$xy(x,yX)(bB)(b=\{x,y\})$$

By transfer, this becomes for a nonstandard graph $`{}_{}{}^{}G=\{^{}X,^{}B\}`$

$$xy(x,y^{}X)(b^{}B)(b=\{x,y\})$$

Alternatively, under an ultrapower construction, we have for $`{}_{}{}^{}G=[G_n]=[\{X_n,B_n\}]`$ that $`x=[x_n]^{}X`$ and $`y=[y_n]^{}X`$ are adjacent (i.e., $`xy`$) if there exists a $`b=[b_n]^{}B`$ such that $`\{n:b_n=\{x_n,y_n\}\}`$.

Adjacency between edges: For a standard graph, two edges $`b,cB`$ are called adjacent and we write $`bc`$ when the following sentence on the right-hand side of $``$ is true.

$$bc(b,cB)(xX)(xbxc)$$

By transfer, we have for nonstandard edges $`b`$ and $`c`$

$$bc(b,c^{}B)(x^{}X)(xbxc)$$

Under an ultrapower approach, we would have $`b=[b_n]`$ and $`c=[c_n]`$ are adjacent nonstandard edges when there exists a nonstandard vertex $`x=[x_n]`$ such that

$$\{n:x_nb_n\mathrm{and}x_nc_n\}.$$

4. Nonstandard Hyperfinite Paths and Loops

Again, we start with a standard graph $`G=\{X,B\}`$. Remember that since $`B`$ is a set of two-element subsets of $`X`$, all edges are distinct (i.e., there are no multiedges) and there are no self-loops. A finite path $`P`$ in $`G`$ is defined by the sentence

$$(kIN\{0\})(x_0,x_1,\mathrm{},x_kX)(b_0,b_1,\mathrm{}b_{k1}B)$$

$$(x_0b_0b_0x_1x_1b_1b_1x_2\mathrm{}x_{k1}b_{k1}b_{k1}x_k)$$
(1)
That all the vertices and edges in $`P`$ are distinct is implied by the fact that those $`k`$ vertices in $`X`$ and those $`k1`$ edges in $`B`$ are perforce all distinct. The length $`|P|`$ of $`P`$ is the number of edges in $`P`$; thus, $`|P|=k`$.

We may apply transfer to (1) to get the following definition of a nonstandard path $`{}_{}{}^{}P`$.

$$(k^{}IN\{0\})(x_0,x_1,\mathrm{},x_k^{}X)(b_0,b_1,\mathrm{}b_{k1}^{}B)$$

$$(x_0b_0b_0x_1x_1b_1b_1x_2\mathrm{}x_{k1}b_{k1}b_{k1}x_k)$$
(2)
In this case, the length $`|^{}P|`$ equals $`k^{}IN\{0\}`$; in general, $`k`$ is now a positive hypernatural number. We therefore call $`{}_{}{}^{}P`$ a hyperfinite path. To view this fact in terms of an ultrapower construction of $`{}_{}{}^{}G=[G_n]`$, note that the $`G_n`$ may be finite graphs growing in size or indeed be conventionally infinite graphs. Thus, $`{}_{}{}^{}P`$ may have an unlimited length, that is, its length may be a member of $`{}_{}{}^{}ININ`$.

A standard loop is defined as is a standard path except that the first and last vertices are required to be the same. Upon applying transfer, we get the following definition of a nonstandard loop.

$$(k^{}IN\{0\})(x_0,x_1,\mathrm{},x_{k1}^{}X)(b_0,b_1,\mathrm{}b_{k1}^{}B)$$

$$(x_0b_0b_0x_1x_1b_1b_1x_2\mathrm{}x_{k1}b_{k1}b_{k1}x_0)$$
(3)
5. Connected Nonstandard Graphs

A standard graph $`G=\{X,B\}`$ is called connected if, for every two vertices $`x`$ and $`y`$ in $`G`$, there is a finite path (1) terminating at those vertices, that is, $`x_0=x`$ and $`x_k=y`$. Let $`𝒞`$ denote the set of connected standard graphs, and let $`𝒫(G)`$ be the set of all finite paths in a given standard graph $`G`$. Also, for any $`P𝒫(G)`$, let $`x_0(P)`$ and $`x_k(P)`$ denote the first and last nodes of $`P`$ in accordance with (1); $`k`$ depends upon $`P`$. Then, the connectedness of $`G`$ is defined symbolically by the truth of the following sentence to the right of $``$.

$$G𝒞(x,yX)(P𝒫(G))((x_0(P)=x)(x_k(P)=y))$$
(4)
By transfer, we obtain the definition of the set $`{}_{}{}^{}𝒞`$ of all connected nonstandard graphs: For $`{}_{}{}^{}G=\{^{}X,^{}B\}`$, for $`{}_{}{}^{}𝒫(^{}G)`$ being the set of nonstandard paths $`{}_{}{}^{}P^{}G`$, and for $`x_0(^{}P)`$ and $`x_k(^{}P)`$ being the first and last vertices of $`{}_{}{}^{}P`$, we have

$${}_{}{}^{}G^{}𝒞(x,y^{}X)(^{}P^{}𝒫(^{}G))((x_0(^{}P)=x)(x_k(^{}P)=y))$$
(5)
Here, $`k^{}IN\{0\}`$ as in (2).

Let us explicate this still further in terms of an ultrapower construction of $`{}_{}{}^{}G=[G_n]`$ from an equivalence class of sequences of (possibly infinite) graphs, $`G_n`$ being one of those sequences. With $`{}_{}{}^{}P=[P_n]`$ denoting a nonstandard path obtained similarly from a representative sequence $`P_n`$ of finite paths, $`P_n`$ being in $`G_n`$, we let $`x_0(P_n)`$ and $`x_k(P_n)`$ denote the first and last vertices of $`P_n`$. (Thus, $`k`$ also depends on $`n`$ of course.) Then, $`x_0(^{}P)=[x_0(P_n)]`$ and $`x_{}_{}{}^{}k(^{}P)=[x_k(P_n)]`$ are the first and last nonstandard vertices of $`{}_{}{}^{}P`$. (In (5), $`{}_{}{}^{}k`$ is denoted by $`k^{}IN\{0\}`$.) Then, $`{}_{}{}^{}G`$ is called connected if and only if, given any nonstandard vertices $`{}_{}{}^{}x=[x_n]`$ and $`{}_{}{}^{}y=[y_n]`$ in $`{}_{}{}^{}G`$, we have that, for almost all $`n`$, there exists a finite path $`P_n`$ terminating at $`x_n`$ and $`y_n`$. This can be restated by saying that there exists a hyperfinite path $`{}_{}{}^{}P`$ in $`{}_{}{}^{}G`$ terminating at $`{}_{}{}^{}x`$ and $`{}_{}{}^{}y`$.

Later on, we will need a special case of $`{}_{}{}^{}𝒞`$: Let $`𝒞_f`$ denote the subset of $`𝒞`$ consisting of all finite connected standard graphs $`G=\{X,B\}`$, where $`|X|IN\{0,1\}`$, $`|B|IN\{0\}`$. Then, $`{}_{}{}^{}𝒞_{f}^{}`$ is the subset of $`𝒞`$ obtained by lifting $`𝒞_f`$ through transfer to a subset of $`{}_{}{}^{}𝒞`$. In this case,

$${}_{}{}^{}G^{}𝒞_f(^{}G=\{^{}X,^{}B\}^{}𝒞)(|^{}X|^{}IN\{0,1\}|^{}B|^{}IN\{0\}).$$
(6)
We call such a $`{}_{}{}^{}G`$ a nonstandard hyperfinite connected graph.

6. Nonstandard Subgraphs

If $`A`$ and $`C`$ are sets of vertices with $`AC`$ , we get upon transfer the following definition for sets of nonstandard vertices.

$${}_{}{}^{}A^{}C(x^{}A)(x^{}C)$$

Our purpose in this section is to define a nonstandard subgraph $`{}_{}{}^{}G_{s}^{}`$ of a given nonstandard graph $`{}_{}{}^{}G`$. We let $`𝒢`$ denote the set of all standard graphs. By definition, $`G_s=\{X_s,B_s\}`$ is a (vertex induced) subgraph of $`G=\{X,B\}𝒢`$ if $`X_sX`$ and $`B_s`$ is the set of those edges in $`B`$ that are each incident to two vertices in $`X_s`$. Let us denote the set of all such subgraphs of $`G`$ by $`𝒢_s(G)`$. Then, symbolically $`G_s`$ is defined by

$$G_s𝒢_s(G)$$

$$(G_s=\{X_s,B_s\}𝒢)(G=\{X,B\}𝒢)$$

$$((X_sX)(B_s=\{b=\{x,y\}B:x,yX_s\})).$$

By transfer, we get the definition of a nonstandard subgraph $`{}_{}{}^{}G_{s}^{}`$ of a given nonstandard graph $`{}_{}{}^{}G`$. In this case, $`{}_{}{}^{}𝒢`$ denotes the set of all nonstandard graphs, and $`{}_{}{}^{}𝒢_{s}^{}(^{}G)`$ denotes the set of all nonstandard subgraphs of a given $`{}_{}{}^{}G^{}𝒢`$.

$${}_{}{}^{}G_{s}^{}^{}𝒢_s(^{}G)$$

$$(^{}G_s=\{^{}X_s,^{}B_s\}^{}𝒢)(^{}G=\{^{}X,^{}B\}^{}𝒢)$$

$$((^{}X_s^{}X)(^{}B_s=\{b=\{x,y\}^{}B:x,y^{}X_s\})$$

7. Nonstandard Trees

The symbols $`𝒢`$, $`𝒢_s(G)`$, $`𝒞`$, $`𝒞_f`$, and their nonstandard counterparts have been defined above. Now, let $`(G)`$ be the set of all loops in the standard graph $`G`$, and let $`𝒯`$ be the set of all standard trees. Then, a tree $`T=\{X_T,B_T\}`$ can be defined symbolically by

$$T𝒯(T𝒞)(\neg (L(T)))$$
(7)
To transfer this, we let $`{}_{}{}^{}(^{}G)`$ be the set of all nonstandard loops in a given nonstandard graph $`{}_{}{}^{}G`$, as defined by (3), and we let $`{}_{}{}^{}𝒯`$ denote the set of nonstandard trees $`{}_{}{}^{}T`$, defined as follows:

$${}_{}{}^{}T^{}𝒯(^{}T^{}𝒞)(\neg (^{}L^{}(^{}T)))$$
(8)
Next, let $`𝒯_{sp}(G)`$ be the set of all spanning trees in a given finite connected standard graph $`G=\{X,B\}`$. That $`T`$ is such a spanning tree can be expressed symbolically as follows.

$$T𝒯_{sp}(G)$$

$$(G=\{X,B\}𝒞_f)(T=\{X_T,B_T\}𝒯)((T𝒢_s(G))(|X|=|X_T|))$$
(9)
By transfer, we have the set $`{}_{}{}^{}𝒯_{sp}^{}(^{}G)`$ of all spanning trees of a given hyperfinite connected nonstandard graph $`{}_{}{}^{}G`$, defined as follows:

$${}_{}{}^{}T^{}𝒯_{sp}(^{}G)$$

$$(^{}G=\{^{}X,^{}B\}^{}𝒞_f)(^{}T=\{^{}X_T,^{}B_T\}^{}𝒯)((^{}T^{}𝒢_s(^{}G))(|^{}X|=|^{}X_T|))$$
(10)
8. Some Numerical Formulas

With these symbolic definition in hand, we can now lift some standard formulas regarding numbers of vertices and edges into a nonstandard setting. For example, if $`p`$, $`q`$, and $`r`$ are the number of vertices, the number of edges, and the cyclomatic number respectively of a given connected finite graph, then $`r=qp+1`$. Symbolically, this can be stated as follows. Again, we use the notation $`G=\{X,B\}`$ for a graph and $`T=\{X_T,B_T\}`$ for a tree.

$$(p,q,rIN)(G𝒞_f)(T𝒯_{sp}(G))$$

$$((p=|X|q=|B|r=|B||B_T|)(r=qp+1))$$

By transfer, we obtain the following formula in hypernatural numbers.

$$(p,q,r^{}IN)(^{}G^{}𝒞_f)(^{}T^{}𝒯_{sp}(^{}G))$$

$$((p=|^{}X|q=|^{}B|r=|^{}B||^{}B_T|)(r=qp+1))$$

Another standard formula for a connected finite graph having no multiedges is that $`p1qp(p1)/2`$. Symbolically, we have

$$(p,qIN)(G𝒞_f)((p=|X|q=|B|)(p1qp(p1)/2)).$$

So, by transfer, we have

$$(p,q^{}IN)(G^{}𝒞_f)((p=|^{}X|q=|^{}B|)(p1qp(p1)/2)).$$

Still another example of such a lifting concerns the radius $`R`$ and diameter $`D`$ of a finite connected graph $`G`$. It is a fact that $`RD2R`$ \[3, page 37\], \[4, pages 20-21\]. Again, we need to express ideas symbolically.

Let $`AIN`$ be such that $`|A|IN`$ (i.e., $`A`$ is a finite subset of $`IN`$). We use the symbols $`\overline{a}=\mathrm{max}A`$ and $`\underset{¯}{a}=\mathrm{min}A`$ as abbreviations for the following sentences.

$$\overline{a}=\mathrm{max}A(cA)(\overline{a}A)(\overline{a}c)$$

$$\underset{¯}{a}=\mathrm{min}A(cA)(\underset{¯}{a}A)(\underset{¯}{a}c)$$

This transfers to

$$\overline{a}=\stackrel{}{\mathrm{max}}A(c^{}A)(\overline{a}^{}A)(\overline{a}c)$$

$$\underset{¯}{a}=\stackrel{}{\mathrm{min}}A(c^{}A)(\underset{¯}{a}^{}A)(\underset{¯}{a}c),$$

where now $`{}_{}{}^{}A`$ is a hyperfinite subset of $`{}_{}{}^{}IN`$ and $`\overline{a}`$ and $`\underset{¯}{a}`$ are hypernatural numbers. $`{}_{}{}^{}A`$ does have a maximum element and a minimum element so that these definitions are valid \[5, pages 149-150\].

Now, for a given finite connected graph $`G𝒞_f`$ and with $`x`$ and $`y`$ being any two vertices in $`G`$, let $`𝒫_{x,y}`$ denote the set of all paths in $`G`$ terminating at $`x`$ and $`y`$. The length $`|P_{x,y}|`$ of any $`P_{x,y}𝒫_{x,y}`$ is the number of edges in $`P_{x,y}`$. Then, the distance between any two vertices $`x`$ and $`y`$ of $`G=\{X,B\}`$ is the natural number $`\mathrm{min}\{|P_{x,y}|:P_{x,y}𝒫_{x,y}\}`$. So, with $`𝒟(G)`$ denoting the set of distances in $`G`$, we may write

$$d_{x,y}𝒟(G)(x,yX)(P_{x,y}𝒫_{x,y})(d_{x,y}=\mathrm{min}\{|P_{x,y}|𝒫_{x,y}\})$$

If $`x=y`$, we set $`d_{x,x}=0`$. By transfer, we have the enlargement $`{}_{}{}^{}𝒫_{x,y}^{}`$ of $`𝒫_{x,y}`$ consisting of all the nonstandard paths terminating at the nonstandard vertices $`x`$ and $`y`$. We also have the internal set $`{}_{}{}^{}𝒟(^{}G)`$ of all hypernatural distances in $`{}_{}{}^{}G`$:

$${}_{}{}^{}d_{x,y}^{}^{}𝒟(^{}G)(x,y^{}X)(^{}P_{x,y}^{}𝒫_{x,y})(^{}d_{x,y}=\mathrm{min}\{|^{}P_{x,y}|:^{}P_{x,y}^{}𝒫_{x,y}\})$$

Here, too, $`{}_{}{}^{}d_{x,x}^{}=\mathrm{𝟎}`$.

Furthermore, two nonstandard vertices $`x,y^{}X`$ are said to be limitedly distant if $`{}_{}{}^{}d_{x,y}^{}`$ is a limited hypernatural. This defines an equivalence relation on $`{}_{}{}^{}X`$; indeed, reflexivity and symmetry are obvious, and the triangle inequality follows by transfer from the triangle inequality for distances in $`G`$. So, by analogy with galaxies for hyperreals, we might refer to the equivalence classes induced by limited distances as “nodal galaxies”; these partition $`{}_{}{}^{}X`$.

Next, we have the eccentricity $`e_x`$ of any vertex of $`G=\{X,B\}`$ as the maximum of the distances from $`x`$. With $`(G)`$ being the set of eccentricities in $`G`$ and with $`𝒟_x`$ being the set of distances from $`x`$, we have symbolically

$$e_x(G)(existsxX)(e_x=\mathrm{max}\{d_x:d_x𝒟_x\}).$$

So, for a hyperfinite connected graph $`{}_{}{}^{}𝒢=\{^{}X,^{}B\}^{}𝒞_f`$, we have by transfer

$$e_x(^{}G)(x^{}X)(e_x=\mathrm{max}\{d_x:d_x^{}𝒟_x\}),$$

where now $`(^{}G)`$ is the set of hypernatural eccentricities for nonstandard vertices in $`{}_{}{}^{}G`$ and $`{}_{}{}^{}𝒟_{x}^{}`$ is the set of hypernatural distances starting at the nonstandard vertex $`x`$.

Then, for any $`G=\{X,B\}𝒞_f`$, the radius $`R(G)`$ is defined by

$$(e_x(G))(R(G)IN)(R(G)=\mathrm{min}\{e_x:xX\}),$$

which by transfer gives the following definition of the hypernatural radius $`R(^{}G)^{}IN`$ of any $`{}_{}{}^{}G=\{^{}X,^{}B\}^{}𝒞_f`$:

$$(e_x^{}(G))(R(^{}G)^{}IN)(R(^{}G)=\mathrm{min}\{e_x:x^{}X\}),$$

Similarly, the diameter $`D(G)`$ of $`G`$ is defined by

$$(e_x(G))(D(G)IN)(D(G)=\mathrm{max}\{e_x:xX\}),$$

which by transfer gives the hypernatural diameter $`D(G)^{}IN`$ of $`{}_{}{}^{}G`$.

$$(e_x(^{}G))(D(^{}G)^{}IN)(D(^{}G)=\mathrm{max}\{e_x:x^{}X\}),$$

So, we have the following sentence for the standard result:

$$(G𝒞_f)(R(G)D(G)2R(G)),$$

which by transfer yields the nonstandard result

$$(G^{}𝒞_f)(R(^{}G)D(^{}G)2R(^{}G)).$$

9. Eulerian Graphs

A finite trail is defined much as a finite path is defined except that the condition that all the vertices be distinct is relaxed; however, edges are still required to be distinct. Thus, the truth of the following sentence defines a trail $`T`$ in a finite graph $`G=\{X,B\}`$, with $`T`$ having two or more edges. This time we use the notation $`b_m=\{x_m,y_m\}`$ to display the vertices $`x_m`$ and $`y_m`$ that are incident to $`b_m`$.

$$(kIN\{0\})(b_0,b_1,\mathrm{},b_kB)(m\{0,\mathrm{},k1\})(y_m=x_{m+1})$$

That $`B`$ is a set insures that the edges $`b_0,b_1,\mathrm{},b_k`$ are all distinct. On the other hand, this sentence allows vertices to repeat in a trail.

For a closed trail, we have the truth of the following sentence as its definition.

$$(kIN\{0\})(b_0,b_1,\mathrm{},b_kB)(m\{0,\mathrm{},k1\})(y_m=x_{m+1})(y_k=x_0)$$

With $`Q`$ denoting a trail, we denote the set of edges in $`Q`$ by $`B(Q)`$. Also, we let $`𝒬(G)`$ denote the set of closed trails in a given graph $`G=\{X,B\}`$.

By attaching asterisks as usual, we obtain by transfer the corresponding sentence for trails in a given nonstandard graph $`{}_{}{}^{}G=\{^{}X,^{}B\}`$. Thus, a nonstandard trail $`{}_{}{}^{}Q`$ is defined by the truth of the following sentence; now, $`b_m=\{x_m,y_m\}`$ is a nonstandard edge with the nonstandard vertices $`x_m`$ and $`y_m`$.

$$(k^{}IN\{0\})(b_0,b_1,\mathrm{},b_k^{}B)(m\{0,\mathrm{},k1\})(y_m=x_{m+1}).$$

A similar expression holds for a nonstandard closed trail (just append $`(y_k=x_0)`$). With $`{}_{}{}^{}Q`$ denoting a nonstandard trail, we denote the set of nonstandard edges in $`{}_{}{}^{}Q`$ by $`{}_{}{}^{}B(^{}Q)`$. Also, we let $`{}_{}{}^{}𝒬(^{}G)`$ denote the set of nonstandard closed trails in a given nonstandard graph $`{}_{}{}^{}G=\{^{}X,^{}B\}`$.

A finite connected graph $`G=\{X,B\}𝒞_f`$ is called Eulerian if it contains a closed trail that meets every vertex of $`X`$. The degree $`d_x`$ of $`xX`$ is the natural number $`d_x=|\{bB:xb\}|`$. The nonstandard version of this definition is as follows: Given $`{}_{}{}^{}G=\{^{}X,^{}B\}^{}𝒞_f`$, for any $`x^{}X`$, the degree of $`x`$ is $`d_x=|\{b^{}B:xb\}|`$. In this case, $`d_x`$ may be an unlimited hypernatural number when $`{}_{}{}^{}G`$ is a hyperfinite graph. However, $`{}_{}{}^{}G`$ might happen to be a finite graph $`G𝒞_f`$, which from the point of view of an ultrapower construction can occur if all the $`G_n`$ for $`{}_{}{}^{}G=[G_n]`$ are the same finite graph $`G𝒢_f`$; in this case, $`d_x`$ will be a natural number for all $`x^{}X`$.

Let $`_u`$ (resp. $`{}_{}{}^{}_{u}^{}`$) denote the set of all standard Eulerian graphs (resp. nonstandard Eulerian graphs). Then, Eulerian graphs can be defined by asserting the truth of the following sentence to the right of $``$, where as usual $`G=\{X,B\}`$.

$$G_u(Q𝒬(G))((bB)(bB(Q))$$

By transfer, the truth of the following right-hand side defines nonstandard Eulerian graphs. Now, $`{}_{}{}^{}G=\{^{}X,^{}B\}`$.

$${}_{}{}^{}G^{}_u(^{}Q^{}𝒬(G))((b^{}B)(b^{}B(^{}Q)))$$

Now an ancient theorem of Euler asserts that a graph $`G`$ is Eulerian if and only if the degree of every vertex of $`G=\{X,B\}`$ is an even natural number. Symbolically, this can be stated as follows.

$$G_u(xX)(d_x/2IN)$$

Transferring this, we get the nonstandard version of this theorem of Euler:

$${}_{}{}^{}G^{}_u(x^{}X)(d_x/2^{}IN)$$

10. Hamiltonian Graphs

In this section, it is assumed that each graph $`G=\{X,B\}`$ is connected and finite and has at least three vertices (i.e., $`|X|3`$). A graph $`G`$ is called Hamiltonian if it contains a loop that meets every vertex in the graph. Let $`(G)`$ denote the set of all loops in $`G`$. Also, for any loop $`L(G)`$, let $`X(L)`$ denote the vertex set of $`L`$. Then, a Hamiltonian graph $`G=\{X,B\}𝒞_f`$ is also defined by the truth of the following sentence to the right of $``$. The set of Hamiltonian graphs will be denoted by $``$, where $`𝒞_f`$.

$$G(L(G))((xX)(xX(L)))$$

By transfer of this sentence, we define a nonstandard Hamiltonian graph as follows, where now $`{}_{}{}^{}`$ is the set of nonstandard hyperfinite Hamiltonian graphs, $`(^{}G)`$ is the set of all nonstandard loops in $`{}_{}{}^{}G`$, $`{}_{}{}^{}X((L)`$ is the set of nonstandard vertices in $`L(^{}G)`$, and $`{}_{}{}^{}G=\{^{}X,^{}B\}`$.

$${}_{}{}^{}G^{}(L(^{}G))((x^{}X)(x^{}X(L))).$$

A simple criterion for a graph $`G=\{X,B\}`$ to be Hamiltonian is that the degree $`d_x`$ of each of its vertices $`x`$ be no less than one half of $`|X|`$ \[1, page 134\], \[3, page 79\]. Symbolically, this condition is expressed as follows:

$$((xX)(d_x|X|/2))𝒢.$$

By transfer, we get the following criterion for a nonstandard Hamiltonian graph.

$$((x^{}X)(d_x|^{}X|/2))^{}𝒢^{}.$$

A more general criterion due to Ore asserts that $`G=\{X,B\}`$ is Hamiltonian if, for every pair of nonadjacent vertices $`x`$ and $`y`$, $`d_x+d_y|X|`$ \[1, page 134\], \[3, page 79\]. Symbolically, we have

$$((x,yX)((\neg (xy))(d_x+d_y|X|)))G,$$

which by transfer becomes

$$((x,y^{}X)((\neg (xy))(d_x+d_y|^{}X|)))^{}G^{}.$$

Still more general is Posa’s theorem \[1, page 132\], \[3, page 79\]: If, for every $`jIN`$ satisfying $`1j<|X|/2`$, the number of vertices of degree no larger than $`j`$ is less than $`j`$, then the graph $`G=\{X,B\}`$ is Hamiltonian. The following symbolic sentence states this criterion.

$$((jIN)(xX)((1j<|X|/2)(|\{xX:d_xj\}|<j)))G$$

By transfer the following criterion holds for nonstandard graphs $`{}_{}{}^{}G=\{^{}X,^{}B\}`$.

$$((j^{}IN)(x^{}X)((1j<|^{}X|/2)(|\{x^{}X:d_xj\}|<j)))^{}G^{}$$

11. A Coloring Theorem

A simple graph-coloring theorem that is not restricted to planar graphs asserts that, if the largest of the degrees for the vertices of a graph $`G=\{X,B\}`$ is $`k`$, then the graph is $`(k+1)`$-colorable \[6, page 82\].222There exists a function $`f`$ that assigns to each vertex one of $`k+1`$ colors such that no two adjacent vertices have the same color. To express this symbolically, first let $`M(X,IN_{k+1})`$ denote the set of all functions that map a set $`X`$ into the set $`IN_{k+1}`$ of those natural numbers $`j`$ satisfying $`1jk+1`$. Then, the following restates this theorem for the given graph $`G`$.

$$(kIN)(x,yX)$$

$$((d_xk)((fM(X,IN_{k+1}))((xy)(f(x)f(y)))))$$

To transfer this, we first let $`{}_{}{}^{}M(^{}X,IN_{k+1})`$ be the set of all internal functions mapping the enlargement $`{}_{}{}^{}X`$ into $`IN_{k+1}`$. Then, this theorem is transferred to nonstandard graphs simply by appending asterisks, as usual:

$$(kIN)(x,y^{}X)$$

$$((d_xk)((^{}f^{}M(^{}X,IN_{k+1}))((xy)(^{}f(x)^{}f(y)))))$$

Note here that the assumption of a natural-number bound $`k`$ on the degrees of all the nonstandard vertices has been maintained. This conforms to the fact that the enlargement of the finite set $`IN_{k+1}`$ is $`IN_{k+1}`$. As a consequence, the conclusion remains strong.

On the other hand, we could generalize this transferred theorem as follows: In terms of an ultrapower construction, we could replace $`IN_{k+1}`$ by an internal set $`{}_{}{}^{}IN_{k+1}`$ obtained from a sequence $`IN_{k_n+1}:nIN`$ of finite sets $`IN_{k_n+1}`$, one set for each $`G_n`$ with regard to $`{}_{}{}^{}G=[G_n]`$ and with $`k_n`$ being the maximum vertex degree in $`G_n`$. But then, our conclusion would be weakened to a coloring with a hypernatural number $`{}_{}{}^{}k=[k_n]`$ of colors.

12. A Final Comment

Undoubtedly, other standard results for graphs can be lifted in this way to nonstandard settings.