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

Planar graph with a chromatic number of 4 where all vertices have a degree of 4.

Is it possible to have a planar graph with a chromatic number of $4$ such that all vertices have degree $4$? Every time I try to make the degree condition to work on a graph, it loses its planarity.
0
votes
1answer
120 views

Graphs of different orders( at different powers)

Given a connected graph $G =(V,E)$ and a positive integer $k$, the k-th power of $G$, denoted $G^k$ , is the graph whose set of nodes is $V$ and where vertices $u$ and $v$ are adjacent in $G_k$ ...
0
votes
2answers
471 views

All connected planar graph with girth at least 6 are 3-colourable

I'm having trouble with this question. I need to prove that all connected planar graphs with girth at least 6 are 3-colourable. I know that a girth of 6 means that the smallest cycle in a graph is 6 ...
1
vote
3answers
1k views

Minimum degree of a graph at least $\frac{1}{2}(n-1)$ implies connectedness

A few days ago I began a foray into graph theory on a whim, using a discrete mathematics book that I picked up a while ago. I'd like a HINT for this problem, if someone would be so inclined as to ...
1
vote
1answer
428 views

Connected planar graph with girth $\leq$ 6 $\rightarrow$ exists at least one vertex degree $\leq 2$

Having trouble with how to approach this question: Suppose $G$ is a connected planar graph having girth at least $6.$ Prove that $G$ has at least one vertex with degree at most $2.$
3
votes
4answers
535 views

Finding minimal cost edge cover for a bipartie graph

I have got two sets of elements and a pruned graph of bipartie edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
3
votes
3answers
244 views

Counting directed acyclic graphs with the same partial ordering

We are given a partially ordered set $P$. Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes). We want to count the number of ...
2
votes
1answer
447 views

Sum of the eigenvalues of adjacency matrix

Let $G$ be a simple undirected graph with $n$ vertices, and let $A_G$ be the corresponding adjacency matrix. Let $\kappa_1, \dots , \kappa_n$ be the eigenvalues of the adjacency matrix $A_G$. I have ...
2
votes
3answers
258 views

Prove complement of this 12-vertex graph is a tree

Let G12 be a simple graph of 12 vertices, and H12 its complement. It is known that G12 has 7 vertices of degree 10, 2 vertices of degree 9, 1 vertex of degree 8 and 2 vertices of degree 7. Prove or ...
3
votes
2answers
124 views

Finding a High Bound on Probability of Random Set

first time user here. English not my native language so I apologize in advance. Taking a final in a few weeks for a graph theory class and one of the sample problems is exactly the same as the ...
3
votes
1answer
486 views

Simple explanation of Comb inequalities in TSP

A comb can be defined by a handle $H$ and a number of teeths $T_1,T_2,\dots,T_t$ such that: $H,T_1,T_2,\dots,T_t \subseteq V$ $T_j \setminus H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$ $T_j ...
3
votes
2answers
234 views

2- or 3-vertex-connected cubic planar bipartite graphs with only one Hamilton cycles

Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs. What is the smallest 2- or 3-vertex-connected cubic planar bipartite graph with only one (forward and backward ...
3
votes
0answers
288 views

Planar graphs all equivalent to null graph by equivalence relation.

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. Consider any planar graph that is not necessarily connected, but ...
6
votes
2answers
211 views

Probability of Selecting A Random Set in Graph with $k$ Edges That is Independent.

In a graph with $k$ edges, if we pick every vertex randomly and independently with a probability of $\frac{1}{2}$, prove that the probability that this set of randomly chosen vertices is an ...
3
votes
0answers
42 views

Card game problem [duplicate]

Possible Duplicate: A less challenging trivia problem There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and ...
3
votes
2answers
648 views

Proving a graph has no bridges

Having a bit of trouble with this question: Suppose G is a 4-regular connected graph with a planar embedding such that every face has degree 3 or 4, and further that any 2 adjacent faces have ...
3
votes
2answers
279 views

A less challenging trivia problem

There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and each number occurs on exactly two cards. At a signal, each person ...
0
votes
1answer
210 views

Trivia math question

I invite 10 couples to a party to my house. I ask everyone present, including my wife, how many people they shook hands with. It turns out that everyone questioned - I didn't question myself of course ...
3
votes
0answers
212 views

Does Kolmogorov 0-1 law apply to every translation invariant event?

Let $\Lambda$ be a lattice in $\mathbb{R}^d$, $d \ge 2$, thought of as an infinite graph. In percolation theory we consider properties random subgraphs of $\Lambda$. In site percolation $\Lambda^s_p$ ...
5
votes
1answer
4k views

Radius, diameter and center of graph

The eccentricity $ecc(v)$ of $v$ in $G$ is the greatest distance from $v$ to any other node. The radius $rad(G)$ of $G$ is the value of the smallest eccentricity. The diameter $diam(G)$ ...
0
votes
1answer
235 views

When does the adjacency matrix of a graph have an eigenvalue zero?

When does the adjacency matrix $A$ of an undirected graph $G$ not have full rank? Is there any intuition to understanding this?
2
votes
0answers
243 views

First Order logic with vertex covers

Let $G=(V,E)$ be a directed graph. Let $E$ be a binary relation such that $(x,y) \in E$ iff there is an edge from vertex $x$ to vertex $y$. Let the world of first order interpretation be the set of ...
1
vote
0answers
75 views

Quasiconvex and quasiconcave graphs

Can anyone show the difference between quasiconvex, quasiconcave and quasilinear graphs? I am confused, because all quasiconvex graphs seem to be quasilinear...
2
votes
1answer
151 views

Can a planar graph without two triangles that share an edge have a chromatic number larger than 3?

Let G be a square with one diagonal. Are there any planar graphs without G as a subgraph that are not 3-colourable?
5
votes
1answer
2k views

Induced subgraphs

I'm a little confused on the part of "induced" does this mean that from the set of vertices and set of edges that are given, that every vertex is connected to every other vertex? Or for instance, what ...
1
vote
1answer
106 views

Draw the composition of directed graphs?

Given a directed graph representing a relation $S$ on a finite set $F$. How do I draw the directed graphs representing the relation $S^2$, $S^3$, $\ldots$? Thanks!
1
vote
3answers
181 views

Simple connected planar graph with $6$ vertex and $12$ edges , each of the face is bdd

A simple connected planar graph with $6$ vertices and $12$ edges. How do we show that each of the face is bounded by three edges?
2
votes
1answer
309 views

Calculate the sum of pairwise distances in a regular circle graph

I have $n$ nodes arranged in a circle, and each node is connected to its nearest $k$ neighbors (i.e. $\frac{k}{2}$ on its left, and $\frac{k}{2}$ on its right) with $k$ being even. The distance ...
-1
votes
2answers
455 views

Graphs, line graph and complement of graph

The line graph $L(G)$ of a graph $G$ is defined in the following way: the vertices of $L(G)$ are the edges of $G$, $V(L(G)) = E(G)$, and two vertices in $L(G)$ are adjacent if and only if the ...
0
votes
1answer
39 views

Determine if subgraph and exhibit if so

Given a graph $G =(V,E)$ and a subset $S⊆V$, the subgraph of $G$ induced by $S$, denoted $\langle S\rangle$ is the subgraph with vertex set $S$ and with edge set $\{(u,v)\mid u,v\in S \mbox{ and } ...
1
vote
3answers
390 views

Restrictions on the faces of a $3$-regular planar graph

I'm new here and I'm having difficulty with this graph theory question. Suppose $G$ is a connected $3$-regular planar graph which has a planar embedding such that every face has degree either $5$ or ...
4
votes
1answer
401 views

Chromatic number $χ(G) > k$ implies existence of path of length $k$

Show that if $G$ is a loopless graph, $k≥1$ is an integer and $χ(G) > k$ then $G$ has a path with $k$ edges. So, we can assume WLOG that $G$ is connected. we're looking for a path $P$ where ...
3
votes
0answers
111 views

The minimal number of triangles or edges whose union is a graph $G$.

Let $G$ be a simple graph of order $n$. If $G$ is triangle-free, then we know that there is a bipartite graph of the same order and the same size. So $G$ has size less than $n^2/4$. Now if it has ...
6
votes
3answers
393 views

$n$-ary trees with $k$-internal nodes - Catalan numbers

It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got ...
1
vote
1answer
2k views

Constructing A Hasse Diagram Using The Covering Relation

I am still having a little difficultly with the covering relation, specifically that when y covers x, $x \prec y$ there is no element in between them, $ x \prec z \prec y$, where x,y, and z are ...
0
votes
1answer
48 views

Individual components of flow along edges in a graph

I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an ...
4
votes
3answers
274 views

Pólya's Enumeration formula and isomers

The hydrocarbon benzene has six carbon atoms arranged at the vertices of a regular hexagon, and six hydrogen atoms, with one bonded to each carbon atom. I know that two molecules are said to ...
1
vote
1answer
2k views

Difference between 'weak' and 'strong' connected (regarding directed graphs)

While studying discrete maths I was having difficult to understand the following definition: Here is a definition about connected graphs from the book Ralph Grimaldi - Discrete and Combinatorial ...
2
votes
0answers
151 views

The matrix $J$(all of whose entries are 1) is a polynomial in the adjacency matrix $A$ of a graph $G$ …

if and only if $G$ is connected and regular. To prove the "only if", assume $J$ is a polynomial in $A$. Then $JA=AJ$. The entries in the $i$th row of $AJ$ are all equal to the sum of the entries in ...
2
votes
1answer
436 views

A path has only two vertices which are not cut-vertices

Prove that a simple undirected graph $G$ is a path if and only if $G$ has exactly two vertices which are not cut-vertices. If $G$ is a path then it is obvious that there only two vertices which ...
2
votes
1answer
318 views

Pólya’s Enumeration Theorem and chemical compounds

The hydrocarbon naphthalene has ten carbon atoms arranged in a double hexagon, and eight hydrogen atoms attached at each of the corners of the hexagons. Naphthol is obtained by replacing one of ...
0
votes
1answer
80 views

Constant $f:[\mathbb{N}]^2\to \{1,2\}$.

Let $[\mathbb{N}]^2$ denote the set collection in size $2$. Now, let $f:[\mathbb{N}]^2\to \{1,2\}$. How can one show that, if we fixing some $n\in \mathbb{N}$, then there exist infinite set ...
0
votes
1answer
147 views

Breadth first search and bipartiteness

I was just wondering what the correlation is between a breadth-first search tree of a graph and that graph being bipartite?
5
votes
1answer
131 views

Bounds on an induced subgraph of a 4-critical graph

I just hate having to come here to ask questions. It's like accepting defeat that you can't solve it yourself.. but I've been trying to solve this for hours and can't find the intuition to solve the ...
2
votes
0answers
128 views

unique maxflow problem

Suppose we have a directed graph, and we want to get the maxflow out of this graph. How can we decide the maxflow of this graph is unique? I have an idea that after we found a maxflow out of the ...
6
votes
3answers
380 views

Are all $4$-regular graphs Hamiltonian

It is easy to show that all connected $2$-regular graphs are Hamiltonian. The Petersen graph is a $3$-regular graph that is not Hamiltonian. Are there any $4$ regular graphs that are not Hamiltonian? ...
0
votes
1answer
147 views

Smallest Imperfect Graph who's chromatic number equals clique number

So I need to find the smallest imperfect graph, $G$ who's chromatic number equals it's clique number. ie: $$\chi(G) = \omega(G)$$ Finding imperfect graphs isn't hard (since finding perfect graphs ...
3
votes
0answers
59 views

topology on a graphs space

Let $\mathcal{G}$ be the set of locally finite, connected rooted graphs $(G,v)$ up to isomorphism $\cong$. Denote by $[G,v]_r$ the sub-graph of $(G,v)$ induced by the vertices at distance $\leq r$ ...
0
votes
1answer
3k views

Prove by induction that every connected undirected graph with n vertices has at least n-1 edges

The problem is in the title. Here is the hint given: In the inductive case, try proof by contradiction. For this proof by contradiction, you may need to use the hand-shake lemma and concept of ...
0
votes
2answers
703 views

Proof related to minimum and maximum degree of vertices of an undirected graph

I don't know how to proceed for this problem. I would appreciate any help. Thanks! Let $\delta$ and $\Delta$ be the minimum and maximum degree of the vertices of an undirected graph G. Show ...