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

1
vote
1answer
6 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 ...
1
vote
1answer
10 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
6 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
14 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
23 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
0answers
12 views

Capacity of the ball growing linearly with its radius

Let $(V,E)$ be an undirected graph and let one vertex be the origin. Consider $(X_n)$ a simple random walk on the graph. Let $d(v,0)$ be the graph distance between $v$ and $0$. Let $A_n$ the set of ...
0
votes
0answers
21 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
17 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
17 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
9 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
43 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
15 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
45 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
22 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
32 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
27 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
31 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
20 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
36 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
41 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
62 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. ...
0
votes
2answers
40 views

graph theory,number of edges

Let $G_n$ be the graph with vertex set all binary strings of length $n$ (binary strings are strings of zeros and one, for example $0110100$ is a binary string of length seven). Two strings are ...
2
votes
0answers
28 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
1
vote
0answers
16 views

Intuition for Laplacian matrix of a graph's eigenvectors and eigenvalues

I am having difficulty finding intuition for Laplacian matrix eigenvalues/vectors in terms of non-regular, non-complete graphs. For example, consider the L, Laplacian, on a graph, G, a set of points ...
1
vote
1answer
28 views

Proving Depth First Search

Let G be a connected graph, and let r ∈ V (G). Prove that G has a spanning tree T such that for every edge of G with ends u and v, either u belongs to the unique path in T with ends v and r, or v ...
0
votes
2answers
20 views

Every tournament conatins a hamiltonian path - question about the proof

There is a proof that every tournament contains a Hamiltonian path and it goes as follows: Let $P$ be a path of greatest length in a tournament $T$, say $P = (v_1,v_2,...,v_k)$. Let's say that there ...
1
vote
2answers
25 views

Graph Theory Edge-Disjoint Spanning Trees

I have the problem: Show that if a graph $G$ contains $k$ edge-disjoint spanning trees, then for each partition $(V_1, V_2, . . . , V_n)$ of $V(G)$, the number of edges of $G$ which have ends in ...
1
vote
0answers
18 views

Why do we care about triangle density and triangle freeness in large graphs?

There seems to be a lot of research done about determining whether large graphs are triangle free or counting the number of triangles. Aside from coloring, why is this important?
2
votes
1answer
32 views

What is an acyclic connected graph in graph theory?

I want to know What it is and whether there is a difference in the definition when looking at undirected and directed graphs?
0
votes
1answer
31 views

Software(online/offline) to draw graph theory graphs

I need a software that can draw graph by taking number of vertices , type of label and edges in the format (x y) as input eg: ...
3
votes
1answer
30 views

Self complementary graph with a pendant vertex

Show that if a self-complementary graph contains a pendant vertex, then it must have at least another pendant vertex. Let $G$ be a graph of order $n$, so it has $n(n-1)/4$ edges, just like its ...
1
vote
1answer
54 views

What are the components of binary strings?

$C_{9}$ is the graph with vertices representing all binary strings of length nine. Two strings are adjacent if and only if they differ in exactly three positions. How can I compute how many components ...
0
votes
1answer
12 views

Proving Welsh-Powell Algorithm

I'm proving a statement of Welsh-Powel Algorithm, that is, A graph can be colored by only using $\max_i (\min(d_i + 1, i))$ colors. I can understand why it contains $d_i$ but cannot understand the ...