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
15 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
16 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
179 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
9 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
7 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
23 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
13 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
31 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 ...
1
vote
2answers
17 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
14 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
16 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
31 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
19 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
13 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
47 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
24 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
35 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
32 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
37 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
42 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
63 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 [on hold]

For each, k, find all the non-isomorphic trees with at most 6 vertices that have maximum degree k.
5
votes
2answers
31 views

“Sparse” k-Colourings of Graphs

Is there a 4-chromatic graph $G$ and a 4-colouring $c$ of $G$ such that for every vertex $v$, the closed neighborhood $N[v] = \{v\} \cup \{ u\ |\ (v,u) \in G \}$ has at most three colours?
1
vote
1answer
12 views

Triangles incident to a node i

I'm trying to use some fragment-based measures for a network. Given an adjacency matrix representing a (large) network how do you calculate the number of triangles that are incident to every node i? ...
0
votes
1answer
16 views

Why does $K_{\chi(H)}(|H|)$ contain the graph H?

Why does $K_{\chi(H)}(|H|)$ necessarily contain the graph H? This is part of the more general question as to why $K_{\chi(H)}(t)$ should contain H for sufficiently large t. Here $K_{r}(t)$ is a ...
0
votes
1answer
23 views

Tournament with at most three major vertices

I've encountered a question in my past year papers for finals tomorrow and I need help in this question. Let $T$ be a tournament of order $n$ at least $4$, and a vertex $v$ in $T$ is called a ...
0
votes
0answers
34 views

If a computer can check 1 million colorings per second, about how long would it take to check all possible three-colorings on 100 vertices?

If we imagine a graph G with 100 vertices, how would we find all possible colorings for G if G(v) = 100? I think that to solve this problem we would start with vertex 1 with 99 edges for the first ...
0
votes
1answer
20 views

How many edges in a graph with $n$ vertices are needed to guarantee it is connected?

A graph $G$ is connected if every pair of vertices in $u,v\in V$ is connected by some path. For an undirected graph with $n$ vertices, how large does the edge set $E$ have to be to guarantee that it ...
1
vote
2answers
13 views

Acyclic Undirected Graph

Let $G=(V,E)$ be an undirected graph. Prove or disprove: If $|E|\le |V| - 1$ then $G$ is acyclic. I am unsure about if this is even true or not in the first place. I know that trees have $n-1$ ...
-2
votes
1answer
24 views

existence of perfect matching in a bipartite graph with special conditions

Claim: Suppose $G(V, E)$ is a bipartite graph where $A\cup B = V$, $|A|=|B|$, every vertex has a even degree $(deg(v) \in \{2,4,6,...\})$ and no vertex is isolated. if this is the case, you can always ...
2
votes
1answer
25 views

Is the adjacency matrix of a given graph (OR any graphs isomorphic to a given graph) a Kronecker product, and if so what are the factors?

I have a few triangular grid graphs that I am trying to express as the direct products of smaller graphs, if possible. ...