Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
8 views

Adjacency matrix on simple graphs

It is known that one of the eigenvalues in the $k$-regular graph is $k$. I have to prove that for a connected graph with eigenvalue $\Delta$, in which $\Delta$ is the maximum degree in G, the graph ...
0
votes
1answer
9 views

Expected value in graph

You are in a directed weighted graph with $N$ $(63 \le N \le 10^6)$ vertices and $M$ $(1 \le N \le 10^6)$ edges and you want to get from $63^{rd}$ to $4^{th}$ vertex. Going through $i^{th}$ edge takes ...
0
votes
1answer
11 views

Is the transitive closure of a circular graph reflexive?

I feel like it is, but couldn't find anything online to support it - suppose the set A={a,b,c} and the relation set R={(a,b),(b,c),(c,a)}, would the transitive closure be reflexive (ie contain (a,a), ...
-2
votes
1answer
26 views

Suppose there are n suns and n moons Show that every sun can be paid with a moon , with each moon a distance less that 106 miles from the sun.

Suppose there are n suns and n moons and every set of moons is within 106 miles from an equal amount of suns. Show that every sun can be paid with a moon , with each moon a distance less that 106 ...
-1
votes
0answers
15 views

Graph Theory - Spanning Trees [on hold]

What is branch in tree? Tree's edge is branch that the subgraph of the tree which is maximal,am I wrong?
0
votes
2answers
31 views

Trouble with a Graph Theory problem about trees

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$. The way my professor showed us for a complete graph was, like this. I just don't know ...
1
vote
0answers
17 views

Graph Decomposition And Linear Algebra

A module in a graph $G$ is a subset $M$ of the vertices such that all the vertices in $M$ have the same neighbourhoods outside of $M$. That is, if $v_1, v_2 \in M$ and $x \not\in M$, then we have ...
0
votes
1answer
17 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
0
votes
2answers
51 views

Minimum number of operations to make all of the strings (objects) the same

Let $A$ be an alphabet, $K$ and $N$ be natural numbers and $X$ be a list of $N$ strings over $A$, each one consisting of $K$ letters. You have one operation ($@f$): convert a string from $X$ to ...
0
votes
0answers
18 views

maxflow-mincut theorem, why no augmenting path implies existence of maxflow

The proof is taken from course Algorithm II, Princeton, coursera. In the proof of iii => i, Why/How iii implies the existence of cut (A, B)?
3
votes
1answer
26 views

Chromatic number $\chi(G)=600$, $P(\chi(G|_S)\leq 200) \leq 2^{-10}$

I am learning martingale and Hoeffding-Azuma inequality recently but do not how to apply the those inequality or theorem here. Let $G=(V,E)$ be a graph with chromatic number 600,i.e. $\chi(G)=600$. ...
3
votes
4answers
286 views

Prove that the graph is connected

I was wondering if someone can help me understand how prove that this graph is connected. Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph ...
0
votes
0answers
10 views

Prove $\chi(G) \leq 1 + \max \lbrace \delta(H) : H \text{ is an induced subgraph of } G \rbrace $ [duplicate]

Prove that for every graph G $\chi(G) \leq 1 + \max \lbrace \delta(H) : H \text{ is an induced subgraph of } G \rbrace $ [$\delta(H)$ is the degree of the smallest degree vertex in H]
0
votes
1answer
10 views

Size of outerplanar graph

If $G$ is an outerplanar graph of order $n \geq 2$ and size $m$, show that $m \leq 2n -3$ [I can show the result for Hamiltonian outerplanar graphs, and I think its posible to extend the result, but ...
0
votes
1answer
29 views

Traveling salesman “with tunnels”

Like everybody on this website it seems, I have a traveling salesman problem. But the traveler wants to visit tunnels, so his exit points are not the entry points, he has to visit all of them, and his ...
0
votes
1answer
15 views

No triangles or rectangles in a Moore graph of diameter 2.

Can somebody explain why there cannot be any triangles or squares in a Moore graph with diameter 2? This was stated without proof in my class.
1
vote
2answers
33 views

cycle in a directed graph

Hi I saw in an R forum the answer: “If the graph has n nodes and is represented by an adjacency matrix, you can square the matrix (log_2 n)+1 times. Then you can multiply the matrix element-wise by ...
2
votes
2answers
19 views

The Petersen graph is 3-connected

This is obvious, but is there a simple/elegant way to show that the Petersen graph has no vertex cuts of size 2? One could just look at all possible vertex cuts of size 2 and observe that they don't ...
0
votes
1answer
6 views

Graph embedding in space: always possible?

Because graph theory is mostly concerned with embeddings on surfaces, I was wondering what would happen if we would consider higher-dimensional objects. My question is: can every graph always be ...
1
vote
0answers
10 views

implication of positive speed of random walk on a graph

Let $(V,E)$ be a vertex-transitive graph and let one vertex be the origin. Let $d(v,0)$ be the graph distance between $v$ and $0$. Consider $(X_n)$ a simple random walk on the graph. Let $A_n$ be the ...
-1
votes
1answer
47 views

Complement of a connected graph on three or more vertices is disconnected [on hold]

Prove or give a counterexample to the following statement: The complement of a connected graph on three or more vertices is disconnected.
2
votes
2answers
34 views

Upper bound for chromatic number

I'd love a hint in this problem, because don't know where to start. For any graph G it follows: $$\chi (G) \le 1 + \max\{ \delta (H):H \text{ is induced subgraph of } G\} $$ where $\delta (H) = \min ...
3
votes
1answer
32 views

Prove $\chi(G) \leq 1+\max\{\delta(H):H \text{ is an induced subgraph} \}$

Prove that for graph any simple graph $G$ we have: $\chi(G) \leq 1+\max\{\delta(H):H \text{ is an induced subgraph} \}$. Take $G$ and remove any vertex $v$ with degree less than $\chi(G)-1$. Do the ...
2
votes
1answer
17 views

Show that the t-cube $Q_t$ is has connectivity t

The t-cube $Q_t$ may be defined as the graph whose vertices are all the binary $t$-tuples. Vertices are adjacent iff they differ in exactly one component. [e.g. in the 3-cube $(0,0,0)$ is adjacent to ...
0
votes
0answers
7 views

Chromatic Polynomial Q_3

How to compute the chromatic polynomial of graph $Q_3$? Is it easy to compute? Can we use the fact $Q_3= Q_2 \times P_2$? Please give an idea.
0
votes
1answer
15 views

No complete graphs could be bipartitle.

How do I prove that the above statement is false? Can anyone give me a hint or so on how to disprove the above statement?
1
vote
2answers
32 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
0
votes
1answer
30 views

Probability that a random graph is connected

Let $V=\{v_1,\dots,v_n\}$ a set of $n$ vertices. Define $\mathcal{G}$ to be the set of all graphs on $V$. $|\mathcal{G}|=2^{\binom{n}{2}}$. What is the probability that a random graph from ...
2
votes
1answer
21 views

Does $G$ have a $(\chi(G)-1)$- regular induced subgraph.

If $G$ is a simple graph which has chromatic number $\chi(G)$ is it true to claim that there is a $(\chi(G)-1)$-regular induced subgraph? I've been trying to prove it. It seems as though it should be ...
3
votes
1answer
22 views

Prove that a simple critically 3-chromatic graph without isolated vertices has $\Delta(G)=2$

Can any one help me prove - A simple critically 3-chromatic graph without isolated vertices has $\Delta(G)=2$. I tried to do it by contradiction and show that if a vertex $v$ has degree 3 or more ...
1
vote
1answer
20 views

Is the disjoint union of 2 copies of the complete bipartite graphs vertex transitive?

Is the disjoint union of $K_{n/4,n/4}$ and $K_{n/4,n/4}$ a vertex transitive graph? I think it is true, but since I failed to come up with a proof I have some doubts about it. Thanks
0
votes
2answers
16 views

Number of trees which has specific vertex as a leaf?

For vertices ${1,2,...n}$, I want to find the number of trees that has vertex $k$ as a leaf. By Cayley's theorem, the number of total trees are $n^{n-2}$. designate vertex k as a leaf. Now all trees ...
0
votes
1answer
13 views

graph theory, economics and learning prerequisites

I'm a undergraduate student of economics and I"d like to know which classes I have to take to get in in graph theory with the purpose to apply it to economic theory. Undergraduate math is sufficient ...
2
votes
3answers
45 views

Combinatorics Question with a rectangular grid

Let $G$ be a rectangular grid of unit squares with $3$ rows ($3$ rows of squares) and $8$ columns. How many self-avoiding walks are there from the bottom left square of to the top left square of $G$ ? ...
0
votes
0answers
17 views

Are these matrix similar?

If two Laplacian matrices have same diagonal entries(say each diagonal element is $a$, in both matrices) and same spectrum. Are these matrices similar?
2
votes
1answer
51 views

Matching in a bipartite graph

Suppose that graph G a bipartite graph and its bipartition is $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $\frac32 x$ and $|A|\leq x^2$, then $G$ has a ...
0
votes
0answers
25 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...
-2
votes
2answers
40 views

Hamiltonian cycle from adjacency matrix [on hold]

I'm finding it quite hard to answer this question I found; any help would be great. Find a Hamiltonian cycle in the graph G whose adjacency matrix is $$\begin{bmatrix} ...
5
votes
1answer
31 views

Connection between chromatic number and independence number of a graph

Is it true that one can always colour a graph G with $\chi(G)$ colours in such a way that one of the colour classes is a maximum possible cardinality independent set? Please prove if it's true. ...
-3
votes
0answers
27 views

Density and girth relation [on hold]

I have a homework assignment and I am clueless on how to tackle the following problem. Every graph with density $\frac{|E|}{|V|} \geq 2$ has girth at most $2 \log n$. Any ideas or clues?
0
votes
1answer
33 views

Does there exist a multigraph with no self-loops which has exactly one vertex of odd degree?

Does there exist a multigraph with no self-loops which has exactly one vertex of odd degree? Context: While I was reviewing the Königsberger problem I wanted to draw a simple example with just one ...
4
votes
0answers
21 views

Behavior of the giant component of an Erdos-Renyi graph near p = 1/n

what is the behavior of an Erdos-Renyi random graph with p = (1 + f(n))/n with $f(n)=o(1)$? If $f(n)=0$ then it has size about $n^{2/3}$, but what if the probability is perturbed slightly, say with ...
2
votes
1answer
38 views

Factorization of graphs vs factorization of trees

I know trees are a very particular kind of graph, a subset of the set of graphs. I would like to know in which way factorization of graphs relates to factorization of trees. Are there theorems ...
1
vote
0answers
43 views

Proving a greedy algorithm can obtain the optimal solution under certain circumstances

For the graph coloring problem: http://en.wikipedia.org/wiki/Graph_coloring I am trying to design a greedy algorithm to solve it fast. The graph is not planar nor forming a particular structure. ...
1
vote
1answer
64 views

Eigen value and Regular Graph (not Strongly Regular graph).

$A,B$ are 2 adjacency matrices of $d$ Regular graphs(not Strongly Regular graphs). I would like to know- 1.Results/ information related to Eigen values of A,B. There is a formula for ...
1
vote
1answer
35 views

Graph Theory - How many regions of an n-sided polygon with all chords added?

The question: Consider an $m-sided$ polygon with all of its chords added, and assume that no more than two of these chords cross at any one intersection point. Make the figure into a planar graph by ...
3
votes
0answers
31 views

How to determine if these graphs are isomorphic?

I had this question on my last Discrete exam: (the missing vertex on graph G is vertex d) I did prove that the graphs were isomorphic, but my teacher said that I matched up my vertices wrong. ...
1
vote
1answer
31 views

Degree sequence on graphs

I think I'm doing something wrong in the following exercise, but I don't know what it is. Let the degree sequence of a graph be: $\vec{d}=(d_1,d_2,\dots,d_n)$, where $d_1\ge d_2\ge...\ge d_n\ge 0$, ...
5
votes
2answers
45 views

Any equivalent to the Four color theorem for non-planar graphs?

The four color theorem: http://en.wikipedia.org/wiki/Four_color_theorem is only valid if the graph is planar. I wonder if there is an analogous theorem that can be used without that hypothesis. ...
0
votes
1answer
27 views

Non-Isomorphic Trees with at most n vertices [closed]

For each, k, find all the non-isomorphic trees with at most 6 vertices that have maximum degree k.