# Tag Info

6

Not sure without more context, but my best guess is the mathematician was Paul Erdős and technique you are talking about is the Probabilistic Method.

5

Let $V_1,V_2$ be a bipartition of $V$ that maximizes the number $t$ of edges between $V_1$ and $V_2$. For a vertex $v$ define the internal degree $d_i(v)$ as the degree of $v$ in its partite set and the external degree $d_e(v)$ as the degree of $v$ to the other partite set. Clearly $d(v)=d_i(v)+d_e(v)$. We have $d_i(v)\leq d_e(v)$: indeed, if ...

5

Proof by induction: For every complete graph $K_{2n}$ with $2n$ vertices, there is a labeling of the edges with ${-1,+1}$ such that every vertex has $n$ edges labeled $+1$ and $n-1$ edges labeled $-1$. The claim is trivially true for the null graph since there are no vertices. For the graph $K_2$, label the single edge $+1$. Take a graph $K_{2n}$ labeled ...

3

This is not true, $\operatorname{Aut}(X)\neq A\ast B$. First, note that the tree you construct is a biregular tree, where $A$ acts by fixing a vertex and permuting its edges (and the trees extending from these edges). The group $B$ acts similarly, and this extends to a faithful action of $A\ast B$. To see that $\operatorname{Aut}(X)\neq A\ast B$, let $A$ ...

3

Let $n$ be the number of vertices of $G$. Then $G^*$ also has $n$ vertices which means $G$ has $n$ faces. Using $V-E+F=2$, we get $$E=2n-2 \,.$$ If $n=2$ then $V=E=2$ which is not possible. Otherwise, the graph is planar and bipartite*, we have $E\leq 2V-4$, and hence $$2n-2 \leq 2n-4$$ contradiction. *We actually only used that $G$ doesn't have any ...

2

Remember the "first theorem of graph theory:" $$\sum_{v \in V(G)} \deg v =2|E(G)|,$$ where $V(G)$ denotes the vertex set and $E(G)$ the edge set. If $\deg v$ is odd for each vertex, what does the above say about the parity (even or odd) of $|V(G)|$? Once you've figured this out, you still need to translate this into a statement about the size of the graph, ...

2

Consider the $9$ vertex. The minimum sum it can be a part of is $1 + 2 + 9 = 12$. Hence the sum of the vertices around $9$ (and including it) is always at least $12$.

2

If f1 is in F2 then take f2 = f1. EDIT as Casteels pointed out, this is ruled out by the wording of the question. Else, T1 - f1 has two connected components say C1 and C2. T2 must have at least one edge from C1 to C2. Take that as f2.

2

You can build an embedding inductively, since the complement of a graph in $\mathbb{R}^3$ is path-connected: Place your vertices at distinct points. Label the edges with some ordering $E_1, E_2,\ldots$, et cetera. Letting $\mathcal{G}_0$ denote the set of vertices, note that $\mathbb{R}^3 \setminus \mathcal{G}_0$ is path-connected. Thus we can represent ...

2

As stated in my comment I am unsure of the distinctions that must be made between embedding undirected graphs and directed graphs. To me it seems that to embed a directed graph you just embed the underlying undirected graph then orient the edges (possibly "splitting" an edge in the the case our directed graph has an edge in both directions between two ...

1

Hint: Embed in $\mathbb{R}^3.$ Start by drawing it on the $x,y$ plane with crossings OK, but make each crossing only at a point, in a reasonably "nice" way. There are then only finitely many such crossings, and perhaps one can move the edges up/down by a small perturbation to eliminate the crossings. (This is only a hint since I don't know if it can be ...

1

EDIT: This answer assumes a path cannot contain repeated edges or vertices. The OP is interested in the case where edges and vertices can be repeated. See comments below. Here is an example of two non-isomorphic graphs $G$ and $H$ with isomorphic 2-step graphs $G^{(2)}$ and $H^{(2)}$.

1

The correct way, it seems to me, would be writing it as follows: $$\sum_{\{i,j\}\in\cal E}i+j$$ The index set is all the edges, and for each edge we sum its two vertices. Of course, this means that the vertices belong to some structure which includes addition. To your second question $\{1,2\}$ is the set with two elements, $1$ and $2$. The set ...

1

Hint: A necessary condition to partition $E(K_n)$ into edge-disjoint Hamiltonian cycles is that $n$ divides the number of edges.

1

Since each Hamiltonian takes away two edges per vertex, an obvious upper bound for the even case is $\frac n2-1$. For the lower bound, use the following construction: If $n=2m+2$, let the vertices be $0,1,2,\ldots,n-2,n-1$. For $d=1,2,\ldots m$, we have a Hamiltonian cycle of all points except $n-1$ by making steps of length $d$ (i.e. there is an edge ...

1

This should work: Let $A'$ be all vertices with in-degree 0, and let $A''$ be their neighbors Add vertices in $A'$ to $A$ Add vertices in $A''$ to $V \setminus A$ Remove $A' \cup A''$ from $G$ and repeat steps 1-3 until the graph is empty Correctness: Since there are no edges between vertices with in-degree 0, property (i) holds for $A'$. As all ...

Only top voted, non community-wiki answers of a minimum length are eligible