# Tag Info

A partial answer : We have $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such that $a \ \mathcal{R} \ a_1 \ \mathcal{R} \ \cdots \ \mathcal{R} \ a_n \ \mathcal{R} \ b$. The relation $ab-1 = c (a + b)$ can be written as $(ac)(bc)=c^2+1$ and can be solves $a=c+d$ and $b=c+ \dfrac{c ^ 2 + 1} d$ where d is a divisor of $c^ 2 ... 2 No, you cannot map an each edge in$G_1$to an arbitrary one in$G_2$. For example the 1-4 edge in your$G_1$connects a degree-3 vertex with a degree-2 vertex, and cannot map isomorphically to the 1-4 edge in$G_2$which goes bewteen the two degree-3 vertices. Rather than having two isomorphic graphs, it seems to be easier to think in terms of how many ... 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 (This is too long for a comment and not part of the answer I gave a year ago, so I'm posting it as a new answer under community wiki.) I made an exhaustive computer search of the solutions for eight people per side and found out that there is really only one unique solution up to symmetries. Stating this fact and showing the structure of the solution might ... 1 Try working it backwards: can you draw$K_{3,3}$, then add the missing edges to get$K_6$, with the missing edges forming a$6$-cycle? Answer: no, because the missing edges must form two$3$-cycles. 1 For the converse I would proceed by contrapositive with the following ideas. (1) Assume$x$and$y$are vertices for which neither is an ancestor of the other. (2) Argue that there is a lowest common ancestor (I am picturing the tree drawn with the root at the top and going downwards) of$x$and$y$, say$a$. (3) Argue that one of$x$and$y$, say$x$is ... 1$\Longleftarrow$: Assume that (a)$x$stands before$y$in the pre-order traversal of$B$and that (b)$x$stands after$y$in the post-order traversal of$B$. Now assume that (c)$x$is not an ancestor of$y$(a proof by contradiction will follow). There are two cases:$y$is an ancestor of$x$: a node$u$isn't visited by pre-order traversal until all ... 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 Is this enough of a proof? I would have to say no. If every face boundary is a cycle of even length, every face has an even degree. This is essentially saying "If X, then X." The catch is that there might be cycles that are not face boundaries. There are no cycles of odd degree and the graph must be bipartite. This is what we need to prove (and we need ... 1 Each vertex has$d$edges and no two vertices in$A$(or$B$) are connected. So in total,$A$has$|A|d$edges coming out of it and$B$has$|B|d$edges going into it. Can those be different? 1 I wanted to vote up the Karolis's answer and add a comment for$d=0$but I don't have enough reputation, so I write an answer. If$d=0$then your graph has no edges. Any partitioning into disjoint sets$A$and$B$would render a legal bipartition, since there are no edges among the vertices in either of the sets. In particular different number of vertices ... 1 Here is an example of two non-isomorphic graphs$G$and$H$with isomorphic 2-step graphs$G^{(2)}$and$H^{(2)}$. 1 Some useful properties : http://en.wikipedia.org/wiki/Bipartite_graph#Properties A graph is bipartite if and only if it has no odd cycle. Also, a graph is bipartite if and only if it is 2-colorable. The rest is up to you :) 1 The eccentricity of every other vertex can be$4$, as looking at a path of length$5$will tell you (there, the third element has eccentricity of$2$, while the edges have an eccentricity of$4$). Can you show that the eccentricity cannot be more than$4$? 1 The problem you describe is a specialization of the 1-center problem on graphs. This problem can be mathematically formulated as follows: Given a graph$G = (V, E)$with node set$V$and edge set$E \subseteq V \times V$with distances$d: E \rightarrow \mathbb{R}$, find the point$xin the graph minimizing \begin{align} \max_{v \in V} d(v, x) \end{align} ... 1 This should work: LetA'$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 ...