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
1answer
57 views

$\max\{\chi(G):G$ embeds on projective plane$\}=6$

My lecture notes in Discrete Mathematics state that $$ \max\{\chi(G) \; : \; G \text{ embeds on projective plane} \}=6, $$ but I have no idea where this comes from. $\chi(G)$ is the chromatic number ...
3
votes
2answers
92 views

Graphs with a polynomial number of shortest paths between any pair of vertices

Let $G$ be a simple undirected graph, and let $s$ and $t$ be two arbitrary vertices of $G$. Even for some rather restricted graph classes, the number of shortest paths between $s$ and $t$ can be ...
0
votes
1answer
77 views

Drawing Planar Graphs

Is it possible to draw a planar graph on 11 vertices in which each face (country) has 3 neighbours? And is there some method after to draw it to confirm that it is in fact indeed planar? I drew some ...
0
votes
1answer
154 views

How many simple graphs on a set of 8 vertices have 6 edges?

I think the total number of edges for a graph with $8$ vertices would be: $n(n-1)/2$ which would yield $28$. total number of set with $28$ elements is $2^{28}$. But I'm not sure how I can limit the ...
2
votes
0answers
70 views

Eigenvalues of adjacent matrix

If $G$ is a regular graph and suppose, the eigenvalues of its adjacent matrix are $-2, -2, -2, -2, 1, 1, 1, 1,$ and $4$. How would you find the number of vertices, edges and degrees of the graph ...
0
votes
1answer
88 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
2
votes
2answers
331 views

Construction of a triangle-free graph of chromatic number $1526$

I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526" It is added not to use results from the chapter about Ramsey Theory. Now my ...
0
votes
2answers
22 views

Construction of two graphs

I would like to know if it is possible to construct two graphs $G,H$ such that $|G|=|H|, e(G)=e(H)$ (means that the two graphs have the same number of vertices and edges) and $\chi(G)>\chi(H)$ ...
1
vote
1answer
64 views

2 colour theorem

Take a square and draw a straight line right across it. Draw several more lines in any arrangement so that the lines all cross the square, and the square is divided into several regions. The task is ...
1
vote
1answer
109 views

Aren't two infinite graphs always identical?

Suppose you have an infinite graph $G$. I assume $G$ to be cubic and planar. No further conditions, so it will be irregular, maybe in the sense of cubic planar version of Rado's graph: Every possible ...
4
votes
1answer
53 views

$K_{2^p+1}$ is not a union of $p$ bipartite graphs

What I want to show is that among $2^p+1$ points in the plane there are three that determine an angle of size at least $\pi(1-1/p)$. I was told I have to start with showing for $n=2^p$ that the graph ...
0
votes
1answer
263 views

show that in a simple graph, any closed walk of odd length contains a cycle

is there anyone can prove me that? actually I didn't understand what does that mean literally? is not a closed walk already a cycle? what does this question mean? thanks in advance.
2
votes
1answer
54 views

A map in which every country has three sides is 3-colourable

I would like to prove that a map in which every country has three sides is 3-colourable unless it is a copy of $K_4$. That $K_4$ is not 3-colourable is clear because the planar complete graph $K_4$ ...
3
votes
1answer
139 views

Prison break: a minimisation problem

Consider a prison with $n$ prisoners. Each cell contains a phone which can be used to call any other cell. Each prisoner has a different piece of information which, when put together, will ...
2
votes
1answer
970 views

Number of Hamiltonian Paths on a (in)complete graph

This question is motivated by a problem on a local programming competition (you can find the original problem statement here: http://maratona.algartelecom.com.br/files/12maratona.zip , problem E on ...
2
votes
2answers
305 views

Question about edge coloring and perfect matchings in regular graphs

On the wiki page for edge coloring says the following two things: "If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges ...
0
votes
1answer
77 views

Does a clique always have a Hamiltonian path?

This isn't homework I'm just preparing for an exam and I came up with this question while I was reviewing the lecture notes.
2
votes
1answer
83 views

Show that $\chi(G)+\chi(G')\ge2\sqrt n$

I want to show that $\chi(G)+\chi(G')\ge2\sqrt n$ where $G'$ is the complement of some graph $G$ of order $n$. I've so far managed to show $\chi(G)+\chi(G')\le n+1$ (probably not too useful) and that ...
1
vote
1answer
19 views

Linear orderings in an undirected graph

A question I am solving requires "any linear ordering of variables in which each variable is assigned before all its children in the tree." The two solutions of the given options are $C-A-B-D-E-F$ ...
3
votes
0answers
46 views

Minimal graph such that the greedy pathing algorithm always terminates

Saw this question languishing on Reddit and decided it could stand a signal boost. Since I'm not familiar with the area, it might be quite elementary, but it's at least interesting from a layman's ...
1
vote
1answer
79 views

Heat equation for a finite graph

Thank you for an interesting website. I would like to construct the heat equation for a finite graph $G$ using basic math concepts. For example, if $G = \mathbb{Z}/m\mathbb{Z}$ then I think of $G$ ...
11
votes
4answers
598 views

Prove that a game of Tic-Tac-Toe played on the torus can never end in a draw. (Graph theoretic solutions only.)

Here's a problem I assigned to my graph theory class. The only caveat is that I insisted that their solutions be entirely graph theoretic. Have fun with it. Prove that a game of Tic-Tac-Toe played ...
3
votes
1answer
219 views

Graph Theory - Leaves vs. # of vertices degree 3+

I am studying Problem 35, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Prove that a tree always has more leaves than vertices of degree at least 3. I feel like ...
0
votes
2answers
139 views

Category theory - where is my error?

In Explicit formula for exponential objects in category of digraphs and its answer we have currying/uncurrying (which I will denote $\sim$ and $-$) as exponential transpose for the category ...
1
vote
0answers
52 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
10
votes
0answers
471 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
7
votes
0answers
111 views

A connection between nonplanar complete graphs and the alternating group?

I went to an undergrad's senior honors thesis presentation a few days ago. She was discussing crossing numbers and mentioned that complete graphs $K_n$ are nonplanar iff $n \geq 5$. ?Coincidentally? ...
1
vote
0answers
30 views

Polynomial-Reduction (Clique)

If we define the language 2CLIQUE = {(G; t) | G is a graph with at least 2 di fferent cliques of size t}. Now if 2CLIQUE ∈ P then CLIQUE should be ∈ P? I need a bit of help understanding this.
1
vote
2answers
1k views

Solution Verification: Maximum number of edges, given 8 vertices

Suppose a simple graph G has 8 vertices. What is the maximum number of edges that the graph G can have? The formula for this I believe is n(n-1) / 2 where n = number of vertices. 8(8-1) ...
0
votes
1answer
121 views

Definition of degeneracy

A graph $G$ is said to be $k$-degenerate if every subgraph of $G$ has a vertex of degree at most $k$. I'm having a difficult time understanding this definition. Wouldn't this just suggest that ...
5
votes
2answers
1k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
2
votes
2answers
137 views

Counting graphs on 5 vertices [duplicate]

If we have the set A with $\#A=5$, how much graphs can be made over A? The solution says $2^{5^2}$, that is exactly the same number of binary relations on A. I initially thought that the ...
0
votes
1answer
81 views

Groetzsch Graph planarity [closed]

(1) Prove that the Groetzsch Graph is not planar.
1
vote
1answer
47 views

Formula for the number of cubic graphs

Cubic graphs form an interesting class of graphs. The are plenty of computational problems that remain NP-complete on this class. Examples include Hamiltonian cycle problem and maximum independent ...
4
votes
1answer
69 views

Is a graph $G$ completely determined (up to labelling) by its spanning trees?

The title is essentially the question. I know that trees can be represented as a topology (equivalently a topological closure operator) on a set -- so I'm wondering if the collection of spanning trees ...
0
votes
1answer
102 views

How to find minimum number of nodes directly connecting all other nodes in a graph?

let graph $G = {V,E}$. I want to find a minimum subset $A$ of $V$ such that all nodes in $A$ directly connect to all nodes in $(V - A)$ PS:- this is different than minimum vertex cover ...
2
votes
1answer
39 views

definition clarification in graph theory

I was studying about Almost Self-Centered Graphs (ASC). ASC graphs are introduced as the graphs with exactly two non-central vertices. Of course, the remaining two vertices are diametrical. My doubt ...
7
votes
3answers
272 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
11
votes
1answer
356 views

What am I getting for Christmas? Secret Santa and Graph theory

I live with four people, who thankfully don't spend much time on maths.se. We decided this year that we'd do a Secret Santa. We can represent the arrangement of who's buying for whom using a directed ...
5
votes
2answers
272 views

Maximum edges in a square free graph

Square free graph : Graphs with minimum cycle length greater than 4. Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order ...
0
votes
1answer
246 views

Number of unicycles on vertex set $[n]$

Given that a unicycle is a simple graph with only one cycle, and let $u_n$ be the number of unicycles on vertex set $[n]$. How do I find a formula for $u_n$?
7
votes
1answer
570 views

Upper bound on $\chi(G)$ for a triangle-free graph

I'm struggling with the following question; For every graph $G$ such that $K_3 \not\subseteq G$ (i.e. $G$ does not contain a triangle), prove that $\chi(G) \leq 2\sqrt{n} +1$ (where $\chi(G)$ ...
1
vote
0answers
155 views

Does this graph operation have a name? Subgraph join?

Given a graph $G$ and two of its subgraphs $A$ and $B$ we define another subgraph, $A+B\subseteq G$ as the subgraph with the following properties, The vertex set of $A+B$ is the union of the vertex ...
0
votes
0answers
46 views

How to prove theorem about consistency of Markov edge process?

How to prove such theorem: Markov edge process $p_E(y_E)$ with respect to DAG $G=(V,E)$ defined as $p_E(y_E) = \prod_{v \in V} p_E\left(y_{E_{\rm out}(v)} \,\big|\, y_{E_{\rm in}(v) } \right) = ...
1
vote
1answer
104 views

Non isomorphic graphs with equal cycle matrices

everyone. I have solved a following problem, the solution seems too simple, so I am suspicious, that I am making a mistake. Would be very greateful, if someone cheked the solution. So, the problem ...
2
votes
0answers
23 views

Edges and genus in graphs

For a planar graph $G = (V, E)$ there is the well known bound $|E| \leq 3|V| - 6$. If instead of $S^2$ $G$ embeds in the orientable surface $S_g$ of genus $2 - 2g$ with minimal $g$, what can be said ...
0
votes
1answer
78 views

Prove that the minimum weight edge, e, which connects a vertex from V1 to V2 must be a part of a minimum spanning tree of G.

Let G be a graph with vertices in the set V partitioned into two sets V1 and V2. Prove that the minimum weight edge, e, which connects a vertex from V1 to V2 must be a part of a minimum spanning tree ...
1
vote
1answer
151 views

How many rooted plane trees tn are there with n internal nodes?

How many rooted plane trees tn are there with n internal nodes? Plane means that left and right are distinguishable (i.e. mirror images are distinguishable), and rooted simply means that the tree ...
8
votes
1answer
3k views

Proof Involving a Problem from “Good Will Hunting”

I don't know if any of you have seen the movie "Good Will Hunting" but there is a particular mathematics problem in the movie that is of interest to be. One of the problems used in the movie is "Draw ...
1
vote
1answer
56 views

Zero divisor graph of commutative ring

Let $R$ be a commutative ring with unity and let $Zd(R)=P_1∪P_2$, where $P_1$ and $P_2$ are maximal (prime) ideals in $Zd(R)$. Let $P_1∩P_2≠{0}$. Show that the diameter of the zero divisor graph ...