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

2
votes
0answers
53 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
3
votes
0answers
102 views

Integer hexagonal grid variations for Harborth

Harborth's conjecture states that every planar graph has a planar drawing in which all edge lengths are integers. I was looking at that, and I wondered what was known about hexagonal grid graphs. For ...
0
votes
1answer
54 views

Why $d(x) + d(y) \le n$ when proving Mantel's theorem

I was going through the Bollobás book on Modern Graph Theory. When proving the Mantel's theorem, that states $n^2/4$ is the lower-bound for having triangles, the proof start from the assumption that: ...
1
vote
0answers
44 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
17
votes
3answers
471 views

Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
3
votes
0answers
40 views

Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
1
vote
0answers
127 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
1answer
79 views

Graph Theory Contest Maths

I have never covered Graph Theory so I've been put into a bit of a quandary over how to do these two questions (I am assuming the second is graph theory, if not I will edit it out of the question). ...
-2
votes
3answers
734 views

Graph isomorphism when all vertices have the same degree

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.
0
votes
1answer
68 views

What does $ \chi(Tree)\leq 2 $ mean in graph theory?

I am reading an article about graphs in English. Does $\chi(Tree)\leq 2$ mean that each node has no more then $2$ children?
2
votes
1answer
129 views

Graph theory question about planar graphs

How can i prove that every planar graph can be expressed as a union of five edge-disjoint forests ? I think I should use theorem that says : ' Every planar graph contains vertex with degree 5 or ...
2
votes
2answers
62 views

Graph theory proof about triangles.

Getting a bit stuck on this question: Prove that if any graph $H$ has $\delta (H)> \frac{n}{2}$ then $H$ contains a triangle. ($\delta (H)$ means the smallest degree of a vertex in H) So far I ...
9
votes
1answer
120 views

Are injections harder to find than surjections?

Given two finite sets $A$ and $B$ with $|A|<|B|$ There are more functions from $B$ to $A$ than from $A$ to $B$ except when $|A|=1$ or $|A|=2,|B|=3,4$. See here for proof. It is also true there are ...
0
votes
1answer
125 views

topological graph theory and the first Betti number

I am confused by a statement: in Wikipedia, In topological graph theory the first Betti number of a graph G with n vertices, m edges and k connected components equals $$m - n + k.$$ I am ...
2
votes
1answer
76 views

Geometry and natural numbers

I can't find the solution to the following problem, any help welcome. One is given a natural number N. One has to find N points on a straight line, and a (N+1)th point which is not on this straight ...
0
votes
1answer
87 views

What does the author mean in his proof “It follows by induction hypothesis” in theorem 2.3 in the given article below..

http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=pdf&nIdA=23384&nIdSesji=-1 What does the author mean in his proof "It follows by induction hypothesis" in theorem 2.3 in the ...
1
vote
0answers
35 views

Expected chromatic number

If $ G = (V, E) $ is an undirected graph where each edge is included with probability $ p \in [0,1] $ is there a way to calculate $\mathbb E[\chi (G)]$ using elementary methods? Or at least establish ...
1
vote
1answer
59 views

Longest path in $n\times n$ grid

Consider an $n\times n$ grid graph. It is easy to construct (self-avoiding) paths in it of length $n(n+2)$, by starting at the upper left corner, going downwards to the lower left corner, going right ...
2
votes
1answer
317 views

Graph Theory: A Tournament Question

First of all, this is a homework question: ...
0
votes
0answers
60 views

Tree-width of a KxK grid

It's well known that the tree-width of a $K\times K$ grid is exactly $K$. However, on the other hand, we know that the tree-width of a chordal graph is the clique number minus 1. The tree-width of a ...
1
vote
1answer
54 views

Path cover in directed graphs

I cannot figure out what this theorem is trying to say: Every directed graph G has a path cover $\mathcal{P}$ and an independent set $\{\mathcal{v}_P | P \in \mathcal{P}\}$ of vertices such ...
0
votes
1answer
35 views

Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
1
vote
1answer
32 views

Is there a name for this graph density measure?

Let $G=(V,E)$ be an undirected graph. We define the following procedure (randomized greedy coloring): Fix some random ordering over the vertices (each permutation will be chosen w.p. $\frac{1}{|V|...
0
votes
0answers
122 views

Graph Theory: prove the defect version of Hall's theorem

i don't really understand the expression delta(A), and i don't understand how exactly and in what way i am supposed to bound the matching number of G.
1
vote
1answer
72 views

G is a bipartite graph, where for every edge e=(a,b)[a,b are in A,B] d(a)>d(b), and d(a)>0, show that there is a matching saturating A

I think the direction is definitely HALL, i tried using induction on the size of S, where S is some subgroup of A, but i wasn't able to complete the process.
0
votes
1answer
64 views

Showing that a graph doesn't contain a Hamiltonian ccle

In the article here it says that A Hamilton circuit cannot contain a smaller circuit within it. ? What is meant by this? I thought this meant that for example if ...
2
votes
2answers
2k views

Maximum no.of edges in a bipartite graph

I have to prove that for a bipartite graph G on n vertices the number of edges in $G$ is at most $n^2/4$. I used induction on n. induction hypothesis:Suppose for a bipartite graph with less than ...
1
vote
1answer
44 views

MST or not without children ?

I've got an undirected weighted graph G with c:E(G)->IR. Now I want to find a spanning tree, such that a node v arbitrary, shall be an internal node, and among all spanning trees, in which v is only ...
10
votes
2answers
275 views

When is the automorphism group of the Cayley graph of $G$ just $G$?

Let $G$ be a finite group and $S$ a generating set of $G$. We can draw the Cayley graph $C(G,S)$ by putting each element of $G$ as a vertex, and drawing an edge between two elements $g$, $h\in G$ iff $...
4
votes
3answers
324 views

Graph Theory book with lots of Named Graphs/ Graph Families

I'm doing a research about an operation on graphs and I am now in the point where I want to apply it to some named graphs or to some of the graph families like paths, cycles, wheels, etc. I am ...
1
vote
0answers
34 views

Strongly regular directed graph and its complementary graph..

I'm reading a paper (Art Duval) about generalizing the strongly regular idea to directed graphs.. anyway, the lemma is: Also, to be clear, the parameters are: $n$ - number of vertices, $k$ - valency, ...
0
votes
1answer
14 views

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets?

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets? My intuition says it's correct because $M,N$ are ...
0
votes
1answer
122 views

Examples of transient and recurrent simple random walks on trees

This is a followup to Recurrence or transience of the 1-3 tree in which I discovered that my original guess of an example for some exercises was wrong. (Those exercises can be found in http://pages.iu....
1
vote
1answer
79 views

Is there a name for graphs that only contain cliques?

I'm wondering if there is a name for graphs such that if there is an edge between vertices A and B and a second edge between vertices B and C then there must be an edge between vertices A and C. My ...
2
votes
1answer
58 views

Recurrence or transience of the 1-3 tree

The 1-3 tree is a rooted tree with only the root at level n=1, and from thereafter, $2^n$ vertices at each tier of distance from the root. However, they are not connected as in the binary tree. Put ...
2
votes
2answers
252 views

Finding the shortest cycle in a graph using every edge

Note: this is homework. Please do not give a complete answer. I've had a brief introduction in graph theory. We have been given to find a shortest cycle visiting all edges and starting and finishing ...
2
votes
2answers
116 views

Show there exists a permutation $a_{i,\sigma (i)} > \frac 1{n^2}$, Hall theorem, doubly stochastic matrix

Question: Let $A = (a_{i,j} )$ be an n by n real matrix, where n > 1, $a_{i,j}$ ≥ 0 for all i, j and the sum of elements in each row of A and the sum of elements in each column of A is exactly 1. ...
2
votes
1answer
34 views

cycle in a product of directed graphs

Does anyone know how to prove that a Cartesian product of two directed graphs $G_1 \times G_2$ has a cycle (not necessarily a Hamiltonian cycle!) if and only if one of the graphs $G_1$ or $G_2$ has a ...
2
votes
0answers
81 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
1
vote
0answers
39 views

Is my induction on euler's formula sufficient? [duplicate]

$n-m+l=2$, where n=#vertices, m=#edges, l=#faces. I've been asked to demonstrate an intuitive, inductive proof (whatever the hell that means). Anyway so I've shown it's true for a tree, where ...
0
votes
1answer
60 views

Bounding the number of vertices in a graph from bellow using minimum degree and girth

I'm going through a graph theory book and apparently the number of vertices should be at least $1+\delta\sum\limits_{i=0}^{r-1}(\delta-1)^i$ for $girth=2r+1$ $2\sum\limits_{i=0}^{r-1}(\delta-1)^i$ ...
1
vote
1answer
77 views

Number of spanning trees in a wheel graph without an external edge.

How many different spanning tree contains n-element graph shown above? Determine the generating function for considered sequence. I am asking for advice.
2
votes
2answers
93 views

Finding an eigenvalue of a special cubic graph

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below: I want to prove that $0$ is an eigenvalue of the adjacency matrix ...
0
votes
1answer
58 views

Perfect matching in line graph

I am given a graph $T$ with an odd number greater than or equal to 3 of vertices. Its line graph $L(T)$ has exactly one perfect matching. I need to prove that if we remove any vertex from $T$, the ...
0
votes
0answers
68 views

Can $n$ vertices be removed so the directed graph contains no cycles?

Given a directed graph and $n\in \mathbb N$ how can we verify if there exists $A \subseteq V$ so that $\left | A \right | \leq n $ and $G-A$ does not contain cycles?
0
votes
1answer
77 views

connected graph with its vertices

Let $ d_1 \leq d_2 \leq \cdots \leq d_n $ be the degrees of the vertices of a graph $G$, and suppose that $d_k \geq k $ for every $ k \leq n − d_n − 1 $. Show that $G$ is connected. I have no idea ...
-2
votes
1answer
54 views

Graphgs Theory: Tree, 2 paths of maximum length intersect at a point [closed]

Justify that in a tree, 2 paths of maximum length intersect at a point.
3
votes
1answer
48 views

Graph Theory : trees, degrees and paths.

Justify that a tree with $n$ vertices that has a vertex of degree $k\gt 2$, hasn't got a path with length bigger than $n-k + 2$
0
votes
2answers
473 views

Prim , Kruskal or Dijkstra

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . ...
5
votes
2answers
1k views

Applications (“in everyday life”) of graph theory

EDIT another idea someone gave me was to consider flows in a network that would not only depend on the node at the beginning and at the end of a vertice but also about the vertice itself, like a ...