Hot answers tagged

4

Wikipedia has a listing of open problems in graph theory.


3

Here are a few that I know of (with overlap of course). It's unclear how up-to-date they are. Douglas West's page: http://www.math.illinois.edu/~dwest/openp/ The Open Problem Garden: http://www.openproblemgarden.org/category/graph_theory Erdos' Problems on Graphs: http://www.math.ucsd.edu/~erdosproblems/


3

Let $G$ be our 2-connected graph, $v$ an arbitrary vertex of $G$. If $G-v$ is still 2-connected, we can take any neighbor of $v$. Otherwise the block tree of $G-v$ has a leaf block $B$. Let $w$ be the (unique) cut vertex of $G-v$ in $B$. $v$ must have a neighbor $u$ in $B-w$, or otherwise $G-w$ would be disconnected(!) Since $B$ is 2-connected, $B-u$ is ...


3

Brinkmann graph has chromatic number 4 and girth 5 (so it has no cycles of length 3 or 4) See https://en.wikipedia.org/wiki/Brinkmann_graph Other such graphs: Foster Cage : http://mathworld.wolfram.com/FosterCage.html Wells graph (again on MathWorld, but I can't post the link...) EDIT, by the way, it has been proved (I think Erdos among the others) ...


3

No. The only two squares that are connected to the top left square are also the only two squares that are connected to the bottom right square. +---+---+---+---+ | A | | | | +---+---+---+---+ | | | Q | | +---+---+---+---+ | | P | | | +---+---+---+---+ | | | | B | +---+---+---+---+ Because the knight's tour needs to pass through A, ...


3

"a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism" .... the below proof is due to Pascal Schweitzer, Theorem 1 (reduction of colored to uncolored graph isomorphism). The graph isomorphism problem for colored graphs polynomial-time reduces to the uncolored graph isomorphism problem. ...


3

As the text is about random graph, I gather that $\Bbb P(\mathcal D)$ is the probability of the event $\mathcal D$. And (as is customary) if the event is given as $\mathcal D=\{\,G\mid d^\max(G)\le n/2\,\}$ for example, we write $\Bbb P(d^\max(G)\le n/2)$ as shorthand for $\Bbb P(\{\,G\mid d^\max(G)\le n/2\,\})$.


2

Ah I found it: Truncated octahedron;


2

Use the following: $$2E = \sum_{k=1}^\infty (2k+1) F_{2k+1}$$ Since every odd length cycle face contributes its edges twice; by Euler's formula $V+F-E=2$ we have: $$2V+2F-4 = 2E$$ $$2\left(V+F-2\right)=\left(\sum_{k=1}^\infty (2k+1)F_{2k+1}\right) $$ The left hand side is even. The right hand side is odd, when an odd number of odd length cycle faces ...


2

You can't do it without trickery. This is known as the three utilities problem and the graph you are trying to draw is $K_{3,3}$ which is known to be non-planar. The types of trickery used are to draw the graph on a torus or to say they are pipelines and one can go over another.


2

As the graph is simple each vertex can have at most $n-1$ edges, of which at there are at most $\lfloor{\dfrac{n-1}{2}}\rfloor$ elements with an even number of edges. For example, if $n=20$, a vertex can have only members of $\{2,4,6,8,10,12,14,16,18\}$ for it's edge count. By the Pigeonhole Principle, $n$ vertices into $\lfloor{\dfrac{n-1}{2}}\rfloor$ ...


1

The following definition of adjacent matrix of directed graphs is stated in 1 : Let $G$ be a directed graph with $V(G) =\{1,...,n \}$. The adjacency matrix $A$ of $G$ is defined in a natural way. Thus, the rows and the columns of $A$ are indexed by $V(G)$: For $i \neq j$; if there is an edge from $i$ to $j$; then $a_{i, j }= 1$, otherwise $a_{i, j ...


1

Hint: If the path from $v$ to $w$ does not contain $e$, we are done. If it does contain $e$, then the path is $v\ldots a b\ldots w$, where $e$ is an edge from $a$ to $b$. But $a$ and $b$ are in a circuit. What does that tell you about the number of ways to get from $a$ to $b$?


1

Every two vertex of a circuit are connected by two different, non-overlapping paths. If we take only one edge out, then we are destroying one of those paths. This, we can still reroute paths which involved getting through 2 vertex of the circuit via the other path.


1

I am not sure if there is a way to assign weights to nodes. Perhaps you can replace each node by an edge with negative weight according to its desirability. Also you can have positive weights on the rest of the edges as usual. Now the problem reduces to the known problem of finding shortest path (least total weight). Algorithms such as Dijkstra or ...


1

You want to write a program finding all the shortest paths between any two vertices in your graph. At the step $n$, the program will have saved in $d[i,j,n]$ the shortest path of length at most $n$. You do it as follows: Initialise $d[i,j,1] = w(i,j)$, that is the length of the edge from $i$ to $j$, if there is any. Proceed recursively: assuming you have ...


1

HINT: If $G$ has more than two components, pick vertices $u$ and $v$ in different components. Say that these components have $n_u$ and $n_v$ vertices, respectively. What is the maximum possible value of $\deg u+\deg v$ in terms of $n_u$ and $n_v$? How does $n_u+n_v$ compare with $n$?


1

First fix the image of $x_0$. There are three possibilities. Since the edge $[x_0,x_1]$ gets mapped to one of the edges connected to the image of $x_0$, you have two choices: you either move clockwise or counter-clockwise. The necessarily also fixes $x_1$. Repeat this decision 20 times, once for each edge. So you have $$ \underbrace{3}_{\text{Number ...


1

The graph doesn't exist since you need the vertex of degree 5 to be connected to all the others (in particular both vertices of degree 1 already have their single neighbor). Now the vertex of degree 4 must be connected to 3 of the vertices with the following degrees: 3,2,1,1. In particular it must be connected to a vertex of degree 1. This is a ...


1

You want the website with the most links. Let $W$ be the website with the most links, suppose there is a website $V$ that can't be reached with $1$ or $2$ clicks from $W$. Then this means if $W$ has a link to website $U$ then $V$ also has a link to website $U$. Since $V$ also has a link to website $W$ we conclude $V$ has more links than $W$, a ...


1

A very useful elementary result in graph theory is the degree sum formula: $$\sum_{v\in V}\deg(v) = 2\lvert E \rvert$$ for a graph $G=(V,E)$. In particular the sum of the degrees of the vertices is even. Now what can you say if some vertex has odd degree?


1

How many edges are there in $G$, in terms of $m$ and $n$? Well, there are $m$-many vertices with $m$-many edges coming out, and $n$-many vertices with $n$-many edges coming out; and this double-counts each edge (since each edge has two endpoints). So the total number of edges is $$m^2+n^2\over 2.$$ Now suppose there is an odd-degree vertex. Do you see why ...


1

My interpretation: The Confusion arises, here- Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $X$ and of $X'$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels ...


1

I am not exactly sure of how your construction works, but I would start looking here. The lexicographic product might be what you are looking for. Hope this helps.


1

A graph with least eigenvalue at least $-1$ is a disjoint union of cliques. (Proof: the least eigenvalue of $K_{1,2}$ is $-\sqrt2$, interlacing.) The graphs with least eigenvalue at least $-2$ were characterized by Cameron, Goethals and Seidel. They are line graphs, so-called generalized line graphs, and a finite set of graphs associated to $E_6$, $E_7$, ...


1

Draw this graph without vertex 10 or 15. Then think of constricting the path 4-20-5-30 down to a single vertex. Remember, you don't need to have $K_{5}$ or $K_{3,3}$ as subgraphs, only a subgraph that is a subdivision of $K_{5}$ or $K_{3,3}$.


1

For the second equation, suppose $L$ is an $n\times n$ Latin square. Construct a graph $X(L)$ with the $n^2$ entries of $L$ as its vertices, with two entries adjacent if they are in the same row, in the same column, or contain the same entry. Then $X(L)$ is a $(3n-3)$-regular graph and, in fact it is strongly regular. Now let $L_1$ be the multiplication ...


1

Try looking at it the other way around: start with a graph that's not complete, and try to find a pair of vertices $a,b$ such that $\chi(G-\{a,b\}) \neq \chi(G)-2$. Then, see if you can figure out how to generalize this approach to arbitrary non-complete $G$.


1

The proof is pretty easy: In any tree $T$ we have $$ |V(T)|= |E(T)|-1$$ where |E(T)| is the number of edges in $T$ Note that $$|E(T)|=\frac{1}{2}\sum_{v\in T} d(v) $$ Then we have two case 1- $ \frac{1}{2}\sum_{v\in T} d(v) $ is odd and thus $ |V(T)|$ is even 2- $ \frac{1}{2}\sum_{v\in T} d(v) $ is even and thus $ |V(T)|$ is also even (Since $d(v)$ is ...



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